PROBABILISTIC AND CONSTRUCTIVE METHODS IN HARMONIC ANALYSIS AND ADDITIVE NUMBER THEORY
Μιχαήλ Κολουντζάκης · 1994
We give several applications of the probabilistic method in harmonic analysis and additive number theory. We also give efficient constructions in place of previous probabilistic (existential) proofs. 1. Using the probabilistic method we prove that there exist nonnegative integers $p\sb1,\...,p\sb{N}$ for which$$\left\vert\min\sb{x}\sum\sbsp{j=1}{N}p\sb{j}\cos jx\right\vert = O(s\sp{1/3}),$$as $s\to\infty,$ where $s = \sum\sbsp{j=1}{N}p\sb{j}.$ This improves a result of Odlyzko who proved a similar inequality with the right hand side replaced by $O((s \log s)\sp{1/3}).$ 2. Similarly we prove that there are frequencies $\lambda\sb1 0$ is an absolute constant. Uchiyama had previously proved this with the right hand side replaced by $C\cdot N\sp{1/2}.$ Furthermore, our proof is constructive. We give a polynomial time algorithm for the selection of such a subsequence. 5. set E of positive integers is called a basis if every positive integer can be written in at least one way as a sum of two elements of E. Using the probabilistic method, Erdos has proved the existence of such a basis E for which every positive integer x can be written as a sum of two elements of E, in at least $c\sb1$ log x and at most $c\sb2$ log x ways, where $c\sb1,c\sb2>0$ are absolute constants. We give an algorithm for the construction of such a basis which outputs the elements of E one by one, and which takes polynomial time to decide whether a certain integer is in E or not. 6. We employ the probabilistic method to improve on some recent results of Helm related to a conjecture of Erdos and Turan on the density of additive bases of the integers. We show that for a class of random sequences of positive integers (which satisfy $\vert A \cap \lbrack 1,x\rbrack\vert\ge C\cdot\sqrt{x}),$ with probability 1, all integers in the interval (1,N) can be written in at least $c\sb1$ log x and at most $c\sb2$ log x ways as a difference of elements of $A \cap \lbrack 1, N\sp2\rbrack.$ Furthermore, let $m\sb{k}$ be a sequence of positive integers which satisfies the growth condition$$\sum\sbsp{k=1}{\infty}{\log m\sb{k}\over\sqrt{m\sb{k}}}<\infty.$$We show that, for the same class of random sequences and again almost surely, there is a subsequence $B\subseteq A, \vert B \cap \lbrack 1,x\rbrack\ge C\cdot\sqrt{x},$ such that, for k sufficiently large, each $m\sb{k}$ can be written in exactly one way as a difference of two elements of B.