\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P6}{19}{2012}

\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{setspace}
%\onehalfspace

\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}

%\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}

\def\leq{\leqslant}
\def\geq{\geqslant}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\C{\mathbb C}
\def\F{\mathbb F}
\def\N{\mathbb N}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\Z{\mathbb Z}
\def\P{\mathbb P}
\def\E{\mathbb E}
\def\eps{\varepsilon}
\def\ro{\varrho}

\title{A basis of finite and infinite sets with small representation function}

\author{Art\=uras Dubickas\\
\small Department of Mathematics and Informatics, Vilnius University,\\[-0.8ex]
\small Naugarduko 24, Vilnius LT-03225, Lithuania\\
\small \texttt{arturas.dubickas@mif.vu.lt}\\
}

\date{\dateline{Nov 7, 2011}{Dec 19, 2011}{Jan 6, 2012}\\
\small Mathematics Subject Classifications: 11B13, 11B34, 11B83,
11R06}

\begin{document}
\maketitle

\begin{abstract}
Let $A$ be a subset of the set of nonnegative integers $\N \cup
\{0\}$, and let $r_A(n)$ be the number of representations of $n
\geq 0$ by the sum $a+b$ with $a,b \in A$. Then $\big(\sum_{a \in
A} x^a\big)^2=\sum_{n=0}^{\infty} r_A(n)x^n$. We show that an old
result of Erd\H{o}s asserting that there is a basis $A$ of $\N
\cup \{0\}$, i.e., $r_A(n) \geq 1$ for $n \geq 0$, whose
representation function $r_A(n)$ satisfies  $r_A(n) < (2e+\eps)
\log n$ for each sufficiently large integer $n$. Towards a
polynomial version of the Erd\H{o}s-Tur\'an conjecture we prove
that for each $\eps>0$ and each sufficiently large integer $n$
there is a set $A \subseteq \{0,1,\dots,n\}$ such that the square
of the corresponding Newman polynomial $f(x):=\sum_{a \in A} x^a$
of degree $n$ has all of its $2n+1$ coefficients in the interval
$[1, (1+\eps)(4/\pi)(\log n)^2]$. Finally, it is shown that the
correct order of growth for $H(f^2)$ of those reciprocal Newman
polynomials $f$ of degree $n$ whose squares $f^2$ have all their
$2n+1$ coefficients positive is $\sqrt{n}$. More precisely, if the
Newman polynomial $f(x)=\sum_{a \in A} x^a$
 of degree $n$ is reciprocal, i.e.,
$A=n-A$, then $A+A=\{0,1,\dots,2n\}$ implies that the coefficient
for $x^n$ in $f(x)^2$ is at least $2\sqrt{n}-3$. In the opposite
direction, we explicitly construct a reciprocal Newman polynomial
$f(x)$ of degree $n$ such that the coefficients of its square
$f(x)^2$ all belong to the interval $[1, 2\sqrt{2n}+4]$.
\end{abstract}

\maketitle

\section{Introduction}

Throughout the paper, let $$\N:=\{1,2,3,\dots\},$$ and let $A$ be a finite or
infinite subset of the set $\N \cup \{0\}$. The square of the
power series
$$f_{A}(x)=\sum_{a \in A} x^a$$ associated with $A$
is given by the formulae
$$f_A(x)^2=\sum_{n=0}^{\infty} r_A(n) x^n,$$ where
$r_A(n)$ stands for the number of representations of the
integer $n \geq 0$ by the sum $a+b$ with $a,b \in A$, namely,
$$r_A(n):=|\{(a,b) \in A^2 \>:\> a+b=n\}|.$$

One of the unsolved conjectures of Erd\H{o}s and Tur\'an \cite{et}
(which is a 500 USD problem in \cite{erdo}) asserts that
$\limsup_{n\to \infty} r_A(n)=\infty$ in case when $A$ is an
asymptotic basis of $\N,$ i.e., $r_A(n) \geq 1$ for each
sufficiently large integer $n$. In general, $A \subseteq \N \cup
\{0\}$ is called a {\it basis} of $B \subseteq \N \cup \{0\}$ if
every element of $B$ belongs to the sumset $$A+A=\{a+a' \>:\> a,a'
\in A\},$$ i.e., $r_A(n) \geq 1$ for each $n \in B$. It is known
that for any $A \subseteq \N \cup \{0\}$ the values of $r_A(n)$,
where $n \geq 0$, cannot all lie in the interval $[1,5]$ (see
\cite{ghhp2}), and in $[1,7]$ (see \cite{bor}). By an entirely
different method, S\'andor \cite{san} showed that the values of
$r_A(n)$, where $n$ runs through all sufficiently large integers,
cannot all lie in the interval $[u,v]$, where $u>(\sqrt{v}-1)^2$.
See also \cite{alon}, \cite{helm1}, \cite{helm2} for some further
work on the Erd\H{o}s-Tur\'an conjecture.

In the opposite direction, Erd\H{o}s in \cite{erdo-1} answered a
question of Sidon and showed that there exists a basis $A$ of $\N
\cup\{0\}$ such that
\begin{equation}\label{vien}
r_A(n) \leq c_1 \log n
\end{equation}
for some positive constant $c_1$ and each $n \geq 2$.
Representations by the sums of $k$ terms have been considered in
\cite{et1}. In \cite{ruzs} Ruzsa proved that there is a basis $A$
of $\N \cup \{0\}$ whose representation function $r_A(n)$ is
bounded on average, namely,
\begin{equation}\label{vienru}
\frac{1}{n} \sum_{k=0}^{n-1} r_A(k)^2 \leq c_2
\end{equation}
for each $n \geq 1$. Recently, Tang \cite{min1} showed that there
is an asymptotic basis $A$ of $\N \cup \{0\}$ for which
\eqref{vienru} holds with the constant $c_2=1449757928$ for each
sufficiently large $n$. He then refined his construction based on an earlier paper
\cite{min3} and
derived the same result with the smaller constant $1069693154$ (see
\cite{min2}). Finally, during the Paul Tur\'an memorial conference
in Budapest Yong-Gao Chen and Quan-Hui Yang (see {\tt
http://www.renyi.hu/$\sim$turan100/abstracts.pdf}) announced that
there is a basis $A$ of $\N \cup\{0\}$ for which \eqref{vienru}
holds with the constant $3000$ for each $n \geq 1$.

The original paper of Erd\H{o}s \cite{erdo-1} is based on some
combinatorial construction with probabilistic flavor.  From there one can get
some explicit but quite large constant $c_1$ in \eqref{vien}.
Our first theorem gives a small constant $2e=5.4365\dots$:

\begin{theorem}\label{ee4}
For each $\eps$ satisfying $0<\eps<1/2$ there is a
positive constant $c(\eps)$ and a basis $A$ of $\N \cup \{0\}$
such that
\begin{equation}\label{logar1}
0.1\eps^2 \log n \leq r_A(n) \leq (2e+\eps)\log n + c(\eps)
\end{equation}
for every $n \geq 2$.
\end{theorem}

In \cite{du1} the author raised a polynomial version of the Erd\H
os-Tur\'an problem. Suppose that $f(x)$ is a polynomial of degree
$n$ with coefficients in $\{0,1\}$ (often called a {\it Newman}
polynomial after \cite{newn}) such that $f(x)^2$ has positive coefficients for
$x^j$, $j=0,1,\dots,2n$. {\it What is the smallest possible maximal coefficient of
$f(x)^2$? Is it bounded or unbounded in terms of $n$?}
Equivalently, we ask for the smallest possible value of
$$\max_{0 \leq k \leq 2n} r_A(k),$$ where $A \subseteq \{0,1,\dots,n\}$
satisfies $A+A=\{0,1,\dots,2n\}$.

Exactly the same question, although without interpretation in terms of
sets and sumsets, can be asked for the polynomial
$f(x)$ of degree $n$ with nonnegative coefficients. Under
additional assumption of $f$ being a {\it reciprocal} polynomial,
namely, $f(x)=x^{n}f(1/x)$, it was proved in \cite{du2} that if the coefficients
of $f(x)^2$ are all at least $1$  then the
largest coefficient of $f(x)^2$ must be at least
$\kappa_{\text{rec}}(n)$, where $\kappa_{\text{rec}}(n) \sim
\frac{2}{\pi} \log n$ as $n \to \infty$. The extremal reciprocal
polynomial with nonnegative coefficients was found explicitly in
\cite{du2}:
\begin{equation}\label{ext}
\sum_{k=0}^{\lfloor n/2 \rfloor } 2^{-2k} {2k \choose k}
x^k+\sum_{k=0}^{n-\lfloor n/2 \rfloor -1} 2^{-2k} {2k \choose k}
x^{n-k}.
\end{equation}
In fact, the first $\lfloor n/2 \rfloor+1$ and the last $\lfloor n/2 \rfloor+1$
coefficients of its square are all equal to $1$ (see \cite{du2}).
We conjectured in \cite{du2} that the extremal polynomial
(with nonnegative coefficients) in the general case should be the
same reciprocal polynomial \eqref{ext}. However, there are no results in
this direction so far (neither for general polynomials with real nonnegative coefficients
nor for Newman polynomials).
Below, we shall give three results of
this type for Newman polynomials.

For a general Newman polynomial we prove that

\begin{theorem}\label{ee5}
For each $\eps>0$ and each integer $n \geq n_0(\eps)$ there is
Newman polynomial of degree $n$ whose square has all of its
coefficients  in the interval $ [1,(1+\eps)(4/\pi)(\log n)^2].$
\end{theorem}

In terms of sumsets Theorem~\ref{ee5} asserts that for each
$\eps>0$ and each sufficiently large $n$ there is subset $A$ of
the set $\{0,1,\dots,n\}$ such that $A+A=\{0,1,\dots,2n\}$ and the
number of representations of each given $k \in \{0,1,\dots,2n\}$
by the sum $a+a'$, with $a,a' \in A$, is at most
$(1+\eps)(4/\pi)(\log n)^2$, i.e.,
$$1 \leq r_{A}(k) \leq (1+\eps)(4/\pi)(\log n)^2$$
for every $k=0,1,\dots,2n$. We remark that under a slightly
weaker assumption
$$\{0,1,\dots,\lfloor (2-\eps)n \rfloor\} \subseteq A+A$$ Theorem~\ref{ee4}
gives a stronger bound with $(\log n)^2$ replaced by $\log n$:

\begin{corollary}\label{ee55} For each $\eps>0$ there is a positive
constant $C=C(\eps)$ such that for every integer $n \geq 2$ there
is a set $A \subseteq \{0,1,\dots,n\}$ for which the sumset $A+A$
contains the set $\{0,1,\dots,\lfloor (2-\eps)n \rfloor\}$ and
$$r_{A}(k) \leq C \log n$$ for every $k=0,1,\dots,2n$.
\end{corollary}


Finally, the next theorem asserts that for a reciprocal Newman polynomial
the correct growth is of the order $\sqrt{n}$:

\begin{theorem}\label{ee-5}
For each reciprocal Newman polynomial $f(x)$ of degree $n$ whose
square has all of its $2n+1$ coefficients at least $1$, the middle
coefficient for $x^n$ in $f(x)^2$ must be at least $2\sqrt{n}-3$.
On the other hand, for each $n \in \N$ there is a reciprocal
Newman polynomial of degree $n$ such that the coefficients of its
square are all in the interval $[1,2\sqrt{2n}+4]$.
\end{theorem}

The first part of Theorem~\ref{ee-5} will be derived by a simple
counting argument, while to prove the second part we shall use the
following explicit example
\begin{equation}\label{expl}
\sum_{i=0}^{t-1} (x^i+x^{n-i}) + \sum_{j=1}^{s}
(x^{jt}+x^{n-jt})+\delta(x),
\end{equation}
where
$$t:=\lfloor \sqrt{n/2}\rfloor, \>\>\>
s:=\lceil n/2t\rceil-1,$$ $$\delta(x):=\begin{cases} 0,
\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>
\text{if} \>\> \{n/2t\} \leq 1/2,\cr x^{n/2},
\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\> \text{if}
\>\> \{n/2t\}>1/2 \>\>\text{and}\>\> n \>\> \text{is even}, \cr
x^{(n-1)/2}+x^{(n+1)/2}, \> \text{if} \>\> \{n/2t\}>1/2
\>\>\text{and}\>\> n \>\> \text{is odd}.
\end{cases}$$

The constants $-3$ and $4$ in Theorem~\ref{ee-5} can be easily
improved. However, we do not know for which constant in the
interval $[2,2\sqrt{2}]$ both parts of Theorem~\ref{ee-5} hold, so
we ask for the best possible constant $\kappa$ for $\sqrt{n}$ in
the sense that for each $\eps>0$ and each sufficiently large $n
\in \N$ the first statement of Theorem~\ref{ee-5} holds with
$(\kappa-\eps)\sqrt{n}$ instead of $2\sqrt{n}-3$ while the second
holds with $(\kappa+\eps)\sqrt{n}$ instead of $2\sqrt{2n}+4$.

In the next section we shall prove Theorem~\ref{ee-5}. Its proof
is independent from  the other parts of the paper. Sections~3 and
4 contain probabilistic and analytic preparation for the proofs of
Theorems~\ref{ee4} and \ref{ee5}. Their proofs will be completed
in Sections~5 and 6, respectively. In Section~5 we shall also
prove Corollary~\ref{ee55}.

\section{Proof of Theorem~\ref{ee-5}}

Let $f(x)$ be a Newman polynomial of degree $n$ whose square
$f(x)^2$ has its coefficients (from the constant coefficient to
the leading coefficient) at least $1$. Let $A$ be the subset of
$B:=\{0,1,\dots,\lfloor n/2 \rfloor \}$ consisting of those
indices $j$ whose coefficients for $x^j$ in $f(x)$ are equal to
$1$. Evidently, the sumset $A+A$ must contain the set $B$. Since
$A+A$ has at most $$|A|(|A|-1)/2+|A|=|A|(|A|+1|)/2$$ distinct
elements, we must have
$$n/2<\lfloor n/2 \rfloor +1 =|B|\leq |A|(|A|+1)/2<(|A|+1)^2/2.$$ Hence
\begin{equation}\label{t12}
|A|>\sqrt{n}-1.
\end{equation}

On the other hand, since $f(x)$ is reciprocal, the middle coefficient of the polynomial
$f(x)^2$ equals
$2|A|-1$ if $n$ is even and $n/2 \in A$, and equals $2|A|$ otherwise. Using \eqref{t12}
we deduce that the coefficient for $x^n$ in $f(x)^2$ is at least
$$2|A|-1 =2(|A|+1)-3 > 2\sqrt{n}-3,$$
as claimed.

Next, we consider the polynomial $f(x)$ given in \eqref{expl} for
$n \geq 18$. Observe first that $$st = t \lceil n/2t-1 \rceil <
t(n/2t)=n/2$$ and
$$n/2-st \leq n/2-(n/2t-1)t=t.$$
The inequality $\{n/2t\}>1/2$ is equivalent to $\lceil n/2t
\rceil<1/2+n/2t$ which is equivalent to $n-st>st+t$, i.e., the gap
between $st$ and $n-st$ is greater than $t$. So if $\{n/2t\} \leq
1/2$ then the gap between $st$ and $n-st$ is at most $t$.  Also,
$t =\lfloor \sqrt{n/2}\rfloor \geq 3$ provided that $n \geq 18$.
It follows that the terms (zero, one or two) of the polynomial
$\delta(x)$ are  between $x^{st}$ and $x^{n-st}$. Consequently,
$f$ is a reciprocal Newman polynomial for each $n \geq 18$.

Since $f(x)^2$ is reciprocal, to prove that all the coefficients
of $f(x)^2$ are at least $1$ it suffices to show that its
coefficients for $x^j$, where $j=0,1,\dots,n$, are nonzero. This
time, let $A$ be the subset of $\{0,1,\dots,n\}$ consisting of
those indices $j$ whose coefficients for $x^j$ in $f(x)$ are equal
to $1$. By \eqref{expl}, we see that
$$A=\{0,1,\dots,t,2t,\dots, st, u_n, v_n, n-st,n-(s-1)t, \dots, n-t,n-t+1,\dots,n\}.$$
Here, $u_n=v_n=0$ if $n-st \leq st+t$. If $n-st>st+t$, then
$u_n=v_n=n/2$ for $n$ even and $u_n=(n-1)/2,$ $v_n=(n+1)/2$ for
$n$ odd. The gaps between consecutive elements
$t,2t,\dots,st,u_n,v_n,n-st,\dots,n-2t,n-t$ of $A$ are at most
$t$. (Here, $u_n, v_n$ are only present if $n-st>st+t$.) Thus each
integer $k \in [0,n]$ belongs to the sumset $A+A$. As $f(x)^2$ is
reciprocal, it follows that all of the coefficients of $f(x)^2$
are at least $1$.

We next show that the coefficients of $f(x)^2$ are at most
$2\sqrt{2n}+5$ for each $n \geq 18$. Since $f(x)^2$ is reciprocal,
it suffices to prove this for the coefficients $a_m$ of $x^m$,
where $0 \leq m \leq n$. Clearly, $a_0=1$, $a_1=2$ and for $m \geq
2$
$$a_m=2|A \cap \{0,1, \dots,\lceil m/2 \rceil-1\}|+\delta_{m/2},$$
where $\delta_{m/2}=1$ for $m$ even and $m/2 \in A$ and
$\delta_{m/2}=0$ otherwise. Hence for each $m=2,\dots,n$
we have
$$a_m=2|A \cap \{0,1, \dots,\lceil m/2 \rceil-1\}|+\delta_{m/2} \leq a_n=2|A \cap
\{0,1, \dots,\lceil n/2 \rceil-1\}|+\delta_{n/2} .$$ It is easy to
see that $a_n=2(s+t)$ if $u_n=v_n=0$, $a_n=2(s+t)+1$ if $u_n=n/2$,
and $a_n=2(s+t+1)$ if $u_n=(n-1)/2$. In the third case, in view of
$s=\lceil n/2t-1 \rceil <n/2t-1/2$ we find that
$$a_n=2(s+t+1) =  2t+2\lceil
n/2t-1 \rceil+2<2t+2(n/2t-1/2)+2=2t+n/t+1.$$
In the first two cases, using $s =\lceil n/2t-1 \rceil  < n/2t$
we obtain the same bound, because then
$$a_n \leq 2(s+t)+1 = 2t+2\lceil
n/2t-1 \rceil+1<2t+2(n/2t)+1=2t+n/t+1.$$

Using $t=\lfloor \sqrt{n/2}\rfloor$, we see that $2t \leq
2\sqrt{n/2}=\sqrt{2n}$ and $t>\sqrt{n/2}-1$. Hence
$$\frac{n}{t} <\frac{n}{\sqrt{n/2}-1} \leq \sqrt{2n} + 3$$ for $n
\geq 18$. Consequently, for $m=2,\dots,n$
$$a_m \leq a_n \leq 2t+n/t+1<\sqrt{2n}+\sqrt{2n}+3+1=2\sqrt{2n}+4.$$
This proves the second part of Theorem~\ref{ee-5} for $n \geq 18$.

To complete the proof observe that for $n=1$ and $n=2$ one can
take the reciprocal Newman polynomial $1+x$ and $1+x+x^2$,
respectively. For $3 \leq n \leq 17$ we may consider the
reciprocal Newman polynomial $f(x)=\sum_{a \in A} x^a$, where
$$A:=\{0,1,2,\dots \lceil n/3\rceil\} \cup \{n-\lceil n/3\rceil,
\dots, n-1, n\}.$$ Then the coefficients of $f(x)^2$ are all at
least $1$ while the largest coefficient of $f(x)^2$ equals
$2\lceil n/3 \rceil + 2$. One can easily verify that this is less
than $2\sqrt{2n}+4$ in the range $3 \leq n \leq 17$.

\section{A bit of probability theory}

Let $X_1, \dots, X_s$ be $s$ independent Bernoulli trials, where
$$\P(X_i=1)=p_i \in [0,1] \>\>\>\> \text{and} \>\>\>\>
\P(X_i=0)=1-p_i$$ for $i=1,\dots,s$. Set $X:=X_1+\dots+X_s$ and
$$\E(X):=\sum_{i=1}^s p_i$$
for the expectation of the random variable $X$. Then Chernoff's
inequality (named after \cite{cher}, see, e.g., \cite{mot})
asserts that

\begin{lemma}\label{chern}
For any $\delta>0$ we have
\begin{equation}\label{up}
\P(X>(1+\delta)\E(X)) \leq
e^{-((1+\delta)\log(1+\delta)-\delta)\E(X)}
\end{equation}
and
\begin{equation}\label{down}
\P(X<(1-\delta)\E(X)) \leq e^{-(\delta+(1-\delta)\log(1-\delta))\E(X)}.
\end{equation}
\end{lemma}

Since $(1+\delta)\log(1+\delta)-\delta>\delta^2/3$ and $\delta+(1-\delta)\log(1-\delta)
>\delta^2/2$ for $0<\delta<1$, inequalities
\eqref{up} and \eqref{down} imply
the following symmetric form of Lemma~\ref{chern}
\begin{equation}\label{che2}
\P(|X-\E(X)|>\delta\E(X)) \leq e^{-\delta^2 \E(X)/2}+e^{-\delta^2 \E(X)/3}
\leq 2e^{-\delta^2 \E(X)/3}
\end{equation}
for every $\delta$ satisfying $0<\delta<1$.

For the proof of Theorems~\ref{ee4} and \ref{ee5} we define
mutually independent random variables $Y_k$ and $Y_k^*$ taking
only values $0$ and $1$, by
$$\P(Y_0=1)=\P(Y_0^*=1)=\P(Y_1=1)=\P(Y_1^*=1)=\P(Y_2=1)=\P(Y_2^*=1)=1$$ and
\begin{equation}\label{ind}
\P(Y_k=1)=\P(Y_k^*=1)=p_k:=\lambda \sqrt{\frac{2 \log k}{\pi k}}
\end{equation}
for each integer $k \geq 3$. Here, $\lambda$ will be chosen in the interval
\begin{equation}\label{lambd}
1<\lambda<2,
\end{equation}
so that $0<p_k \leq p_3<2\sqrt{\frac{2\log 3}{3\pi}} <0.97<1$ for
$k \geq 3$, by \eqref{ind} and \eqref{lambd}. For convenience, we
shall also use the notation $p_0=p_1=p_2=1$, so, by \eqref{ind},
$$\P(Y_k=0)=\P(Y_k^*=0)=1-p_k$$ for every nonnegative integer $k$,
and
\begin{equation}\label{ind1}
p_0=p_1=p_2>p_3>p_4>p_5>p_6>\dots.
\end{equation}

To prove Theorem~\ref{ee4}
we consider the random series
\begin{equation}\label{vi1}
f(x):=\sum_{k=0}^{\infty} Y_k x^k
\end{equation}
with coefficients $0,1$. The square of $f(x)$ is given by
\begin{equation}\label{vi2}
f(x)^2=\sum_{m=0}^{\infty} Z_m x^m,
\end{equation}
 where
\begin{equation}\label{vi3}
Z_m:= 2\sum_{0\leq k <m/2} Y_k Y_{m-k} + Y_{m/2}
\end{equation}
 and throughout the
convention $Y_{m/2}=p_{m/2}=0$ is adopted if $m$ is odd. In the
sum
\begin{equation}\label{vi33}
V_m:=\sum_{0\leq k <m/2} Y_k Y_{m-k}
\end{equation}
the summands $Y_kY_{m-k}$, where $0 \leq k <m/2$, are mutually
independent random variables taking only values $0$ and $1$, so
that Lemma~\ref{chern} is applicable to $X=V_m$.
 By
\eqref{ind}, we have
$$\P(Y_kY_{m-k}=1)=\P(Y_k=1)\P(Y_{m-k}=1)=p_k p_{m-k}.$$ Thus the
expectation of $V_m$ is
\begin{equation}\label{vi4}
\E(V_m)=S_m:=\sum_{0 \leq k < m/2} p_kp_{m-k}.
\end{equation}

In a similar fashion in the proof of Theorem~\ref{ee5} we will
consider the random Newman polynomial
\begin{equation}\label{vi11}
f(x):=\sum_{k=0}^n U_k x^k=\sum_{0 \leq k <n/2} (Y_k x^k+Y_k^*
x^{n-k})+Y_{n/2}x^{n/2},
\end{equation}
where $Y_{m/2}=Y_{m/2}^*=p_{m/2}=0$ if $m$ is odd. Note that
$U_k=Y_k$ for $k \leq n/2$ and $U_k=Y_{n-k}^*$ for $n/2<k \leq n$.
The square of $f$ is given by
\begin{equation}\label{vi21}
f(x)^2=\sum_{m=0}^{2n} Z_m x^m,
\end{equation}
 where
\begin{equation}\label{vi31}
Z_m:= 2\sum_{0\leq k <m/2} U_k U_{m-k} + U_{m/2}
\end{equation}
for $m \leq n$. By symmetry (see \eqref{ind}, \eqref{vi11} and
\eqref{vi21}), for each interval $I \subseteq \R$ we must have
\begin{equation}\label{vi323232}
\P(Z_m \in I)=\P(Z_{2n-m} \in I)
\end{equation}
for $n < m \leq 2n$.

In the sum
\begin{equation}\label{vi311}
V_m:= \sum_{0\leq k <m/2} U_k U_{m-k}
\end{equation}
$U_kU_{m-k}$, where $0 \leq k <m/2$, are mutually independent
random variables taking only values $0$ and $1$, so we will be
able to apply Lemma~\ref{chern} to $V_m$. This time, for $k \leq
n/2$ we have $U_{m-k}=Y_{m-k}$ if $m-k \leq n/2$ and
$U_{m-k}=Y_{n-m+k}^*$ if $m-k>n/2$. Hence, by \eqref{ind},
$$\P(U_k U_{m-k}=1)= \P(Y_kU_{m-k}=1)=\P(Y_k=1)\P(U_{m-k}=1)=p_k p_{\min\{m-k, n-m+k\}}.$$
Thus
the expectation of $V_m$ for $m \leq n$ is
\begin{equation}\label{vi41}
\E(V_m)=T_m:=\sum_{0 \leq k < m/2} p_k p_{\min\{m-k,n-m+k\}}.
\end{equation}


In addition to this we shall also use the Borel-Cantelli lemma
(see, e.g., \cite{fel}).


\begin{lemma}\label{bor}
Let $E_0,E_1,E_2,\dots$ be a sequence of events in some
probability space. If
$$\sum_{j=0}^{\infty} \P(E_j) < \infty$$
then the probability of the event consisting in the occurrence of
only a finite number out of the events $E_j$, $j=0,1,\dots$, is
equal to $1$.
\end{lemma}

Finally, using the notation $E^c=\Omega \setminus E$ for an event
$E$ in the probability space $(\Omega, {\mathcal F},\P)$, from
$\big(\cup_{k=1}^{\ell} E_k \big) \cup \big(\cap_{k=1}^{\ell}
E_k^c \big)=\Omega$
 we obtain the next standard estimate
\begin{equation}\label{bor1}
\P(\cap_{k=1}^{\ell} E_k^c)=1-\P(\cup_{k=1}^{\ell} E_k) \geq
1-\sum_{k=1}^{\ell} \P(E_k).
\end{equation}

\section{...and analysis}

\begin{lemma}\label{l1}
For $S_m$ given in \eqref{vi4} and $p_k$ given in \eqref{ind} we
have
$$
S_m \sim \lambda^2 \log m \>\>\>\> \text{as} \>\>\>\>
m \to \infty.
$$
\end{lemma}

{\em Proof:} Writing
$$\sqrt{\frac{\log k \log (m-k)}{k(m-k)}}=
\frac{1}{m}\sqrt{\frac{(\log m +\log(k/m))(\log m + \log(1-k/m))}
{(k/m) (1-k/m)} }$$ for $3 \leq k \leq m-3$ and replacing the sum
by the corresponding Riemann integral in view of \eqref{ind} we
find that
$$S_m=\sum_{0 \leq k <m/2} p_k p_{m-k} \sim \frac{2\lambda^2 \log m}{\pi}
\int_{0}^{1/2} \frac{dz}{\sqrt{z(1-z)}}$$ $$=\frac{\lambda^2 \log
m}{\pi} \int_{0}^{1} \frac{dz}{\sqrt{z(1-z)}}= \frac{\lambda^2
\log m}{\pi} \frac{\Gamma(1/2)^2}{\Gamma(1)}=\lambda^2 \log m$$ as
$m \to \infty$. (Here, we used the values of the Gamma function
$\Gamma(1/2)=\sqrt{\pi}$ and $\Gamma(1)=1$.) Thus $S_m \sim
\lambda^2 \log m$ as $m \to \infty$, as claimed. $\blacksquare$

\medskip

We next evaluate $T_m$ defined in \eqref{vi41} for $m \leq n$.
(Recall that the probabilities $p_k$ are defined in \eqref{ind}
and $S_m$ is given in \eqref{vi4}.)

\begin{lemma}\label{l2}
We have
\begin{equation}\label{111}
T_m=S_m
\end{equation}
 for $m \leq \lfloor n/2 \rfloor$,
\begin{equation}\label{112}
S_m \leq T_m \leq T_n
\end{equation}
 for $\lfloor n/2 \rfloor<m \leq n$,
and
\begin{equation}\label{114}
T_n \sim (\lambda^2/\pi)(\log n)^2  \>\>\>\> \text{as} \>\>\>\>
n \to \infty.
\end{equation}
\end{lemma}

{\em Proof:} Observe that $p_{\min\{m-k,n-m+k\}}=p_{m-k}$ for $m
\leq \lfloor n/2 \rfloor$. So \eqref{vi4} and \eqref{vi41} yield
\eqref{111}. Assume next that $\lfloor n/2 \rfloor<m \leq n$. Then
$p_{\min\{m-k,n-m+k\}}=p_{n-m+k}$ for $k < m-n/2$ and
$p_{\min\{m-k,n-m+k\}}=p_{m-k}$ for $k \geq m-n/2$. It follows
that
$$T_m=\sum_{0 \leq k <m-n/2} p_{k}p_{n-m+k}+\sum_{m-n/2 \leq k <
m/2} p_kp_{m-k}.$$

Note that, by \eqref{ind1}, the sequence $p_0,p_1,p_2,p_3,\dots$
is nonincreasing. By replacing each $p_{n-m+k}$ is the first sum
by $p_{m-k}$ and using $p_{n-m+k} \geq p_{m-k}$ we obtain $$T_m
\geq \sum_{0 \leq k <m-n/2} p_{k}p_{m-k}+\sum_{m-n/2 \leq k < m/2}
p_kp_{m-k}=\sum_{0 \leq k <m/2} p_{k}p_{m-k} =S_m.$$ Similarly, by
replacing each $p_{n-m+k}$ by $p_k$ in the first sum (so that
$p_{n-m+k} \leq p_k$) of $T_m$ and each $p_{m-k}$ by $p_k$ is the
second sum (so that $p_{m-k}\leq p_k$) of $T_m$, we get $$T_m \leq
\sum_{0 \leq k <m-n/2} p_k^2+ \sum_{m-n/2 \leq k < m/2} p_k^2=
\sum_{0 \leq k < m/2} p_k^2 \leq \sum_{0 \leq k < n/2}
p_k^2=T_n.$$ This completes the proof of \eqref{112}.

To prove \eqref{114} observe that, by \eqref{ind}, we have
$$T_n= \sum_{0 \leq k < n/2} p_k^2 =3+ \frac{2\lambda^2}{\pi} \sum_{3 \leq k<n/2}
\frac{\log k}{k} \sim \frac{\lambda^2} {\pi} (\log n)^2$$ as $n
\to \infty$. $\blacksquare$

\medskip

Recall that if $f(x)=a_0+a_1x+\dots+a_nx^n$ is a polynomial in
$\R[x]$ then its {\it height} and {\it length} are defined by
$$H(f):=\max_{0 \leq j \leq n} |a_j| \>\>\>\> \text{and} \>\>\>\> L(f):=\sum_{j=0}^{n}
|a_j|,$$ respectively. For the infinite series
$f(x)=a_0+a_1x+a_2x^2+\dots$, we define its height by the formula
$$H(f):=\sup_{j \geq 0} |a_j|.$$

\begin{lemma}\label{l3}
Let $f$ be a polynomial (or an infinite series), and let $g$ be a
polynomial. Then $$H((f+g)^2-f^2) \leq (2H(f)+H(g))L(g).$$
\end{lemma}

{\em Proof:} Using $H(fg) \leq H(f)L(g)$ and $H(g^2) \leq
H(g)L(g)$ from the identity $(f+g)^2-f^2=2fg+g^2$ we deduce
$$H((f+g)^2-f^2) \leq 2H(fg)+H(g^2) \leq
2H(f)L(g)+H(g)L(g)=(2H(f)+H(g))L(g),$$ as claimed.
$\blacksquare$



\section{Proof of Theorem~\ref{ee4} and Corollary~\ref{ee55}}


Given $m \geq 3$, let $E_m$ be the event which means that the
random variable $Z_m$ defined in \eqref{vi3} belongs to the union
of intervals
$$[0, 0.1\eps^2 \log m) \cup ((2e+\eps)\log m,\infty).$$
Then $\cap_{i=M}^{\infty} E_i^c$ is the event consisting of
each $Z_m$, $m=M,M+1,\dots$, lying in the interval
$[0.1\eps^2 \log m, (2e+\eps) \log m]$. Selecting
\begin{equation}\label{lambd1}
\lambda:=\sqrt{1+0.18 \eps}
\end{equation}
in \eqref{lambd}
we will show that the
probability of the event $\cap_{i=M}^{\infty} E_i^c$ is positive for some $M$.

By the definition of $E_m$,
\begin{equation}\label{pem12}
\P(E_m) = \P(0 \leq Z_m <  0.1\eps^2 \log m) +\P(Z_m>(2e+\eps) \log
m).
\end{equation}
Let us first estimate the probability of the event $Z_m < 0.1\eps^2
\log m$ from above. Observe that, by \eqref{vi3} and \eqref{vi33},
we have $Z_m=2V_m+Y_{m/2}$. So $V_m<0.05\eps^2 \log m - Y_{m/2}/2$ is
the same event. Evidently, this event is contained in the event
$V_m<0.05\eps^2 \log m$. By \eqref{lambd}, \eqref{vi4} and
Lemma~\ref{l1}, the latter event is contained in the event
$V_m<0.05\eps^2\E(V_m)$ for each sufficiently large $m$.
Hence, by inequality \eqref{down} of Lemma~\ref{chern} applied to
the random variable $X=V_m$ which is the sum of independent
Bernoulli trials with $\delta:=1-\eps^2/20$,
in view of the inequality
\[\delta+(1-\delta)\log(1-\delta)=1-\eps^2/20+(\eps^2/20)\log (\eps^2/20)=
1-(\eps^2/20) \log(20e/\eps^2) >1-0.16\eps\]
which holds for $0<\eps<0.66$,
we deduce that
$$\P(0 \leq Z_m < 0.1\eps^2 \log m) \leq \P(V_m < 0.05\eps^2 \E(V_m))
\leq e^{-(1-0.16\eps)\E(V_m)}.$$ Note that, by \eqref{vi4},
Lemma~\ref{l1} and \eqref{lambd1}, for $m$ large enough we must
have
\[(1-0.16 \eps)\E(V_m)>(1-0.16 \eps)(1+0.1799\eps) \log m > (1+\eps/182)\log m,\]
since $0<\eps<1/2$ implies $(1-0.16 \eps)(1+0.1799\eps)>
(1+\eps/182)$. Consequently,
\begin{equation}\label{viens}
\P(0 \leq Z_m < \eps \log m) \leq m^{-1-\eps/182}<m^{-1-\eps/200}
\end{equation}
for each sufficiently large $m$.

We next estimate the probability of the event $Z_m>(2e+\eps)
\log m$ from above. Once again, by \eqref{vi3} and \eqref{vi33},
we find that  $V_m>(e+\eps/2)\log m - Y_{m/2}/2$ is the same
event. This is contained in the event $V_m>(e+0.49 \eps)\log
m$ for $m$ large enough. The latter event is contained in the
event $V_m>e\E(V_m)$, since, by \eqref{lambd1}, we have
\[\lambda^2=1+0.18\eps<1+0.49e^{-1}\eps=(e+0.49\eps)/e,\]
and so,
by \eqref{vi4} and Lemma~\ref{l1},
$$(e+0.49\eps)\log m>e\E(V_m)$$ for each
sufficiently large $m$.  Therefore, selecting $\delta:=e-1$ in
inequality \eqref{up} of Lemma~\ref{chern} and using
$(1+\delta)\log(1+\delta)-\delta=1$, from Lemma~\ref{l1} and
\eqref{lambd1} we obtain
$$\P(Z_m>(2e+\eps)
\log m) \leq \P(V_m>e \E(V_m)) \leq e^{-\E(V_m)} < e^{-\lambda
\log m}= m^{-\lambda}<m^{-1-\eps/12}$$ for each sufficiently large
$m$. (Here, we used the inequality
$\lambda=\sqrt{1+0.18\eps}>1+\eps/12$ for $0<\eps<1$.)

Combining this upper bound with \eqref{pem12} and \eqref{viens} we
deduce the inequality
$$
\P(E_m) \leq m^{-1-\eps/200}+m^{-1-\eps/12} \leq 2m^{-1-\eps/200}
$$
for each $m \geq m_0$, and so the series $\sum_{m=m_0}^{\infty}
\P(E_m)$ are convergent.  In particular, Lemma~\ref{bor} implies
that for some $M=M(\eps)$ the event $\cap_{i=M}^{\infty} E_i^c$
occurs with positive probability. By the definition of $E_m$, this
means that there exist a series $f(x):=\sum_{n=0}^{\infty} a_n
x^n$, where $a_n \in \{0,1\}$, $a_0=a_1=a_2=1$, such that the
coefficients $b_n$ of its square $f(x)^2=\sum_{n=0}^{\infty} b_n
x^n$  satisfy $$0.1\eps^2 \log n \leq b_n \leq (2e+\eps) \log n$$ for
every $n \geq M \geq 3$.

To complete the proof of the theorem we replace $f(x)$ by the
series
$$f_1(x):=\sum_{n=0}^{M-1} x^n +\sum_{n=M}^{\infty} a_n x^n.$$
Note that the coefficients $c_n$ of its square
$f_1(x)^2=\sum_{n=0}^{\infty} c_n x^n$ are all integers, so they
are all at least $1$, because $c_n \geq b_n >0$ for $n \geq M$ and
$c_n=n+1>0$ for $0 \leq n \leq M-1$. As $\log n < n+1$ for $2
\leq n \leq M$, we clearly have $c_n \geq \log n>0.1\eps^2 \log n$ for each $n
\geq 2$. Since the difference $g(x)=f_1(x)-f(x)$ is a Newman
polynomial of length at most $M-3$, by Lemma~\ref{l3}, we obtain
$$0 \leq c_n-b_n \leq (2H(f)+H(g))L(g) \leq 3L(g) \leq 3(M-3)$$
for every $n  \geq 0$. Thus, setting $b:=\max\{b_0, b_1, \dots,
b_{M-1}\}$, we find that
$$c_n \leq b_n+ 3(M-3)\leq  (2e+\eps) \log n + b+3(M-3)$$ for each $n \geq 0$.
This proves \eqref{logar1} and completes the proof of
Theorem~\ref{ee4}.

To prove Corollary~\ref{ee55} we assume without restriction of
generality that $\eps<1$ and select
$$K:=\lceil 2/\eps \rceil, \>\>\>\> q_0:=\lceil 4/\eps \rceil.$$
To prove the corollary it suffices to show it that holds with some
positive constant $C$ for each $n \geq Kq_0$. Write $n=Kq+r$ with
integers $q \geq q_0$, $r \in \{0,1,\dots,K-1\}$ and consider the
Newman polynomial $p(x):=a_0+a_1x+\dots+a_{q-1}x^{q-1}$ which is
the beginning of the series $f_1(x)$ that are just found in the
proof of Theorem~\ref{ee4}. It is clear that the polynomial
$p(x)^2$ has the coefficients for $x^j$ at least $1$ for
$j=0,1,\dots,q-1$. Also, $$H(p^2) \leq c \log (2\deg p) <c \log
(2q)$$ for some positive number $c$ and each $q \geq 2$.

Consider the Newman polynomial
$$f(x):=p(x)(1+x^q+x^{2q}+\dots+x^{(K-1)q})$$
of degree $$(K-1)q+\deg p \leq (K-1)q+q-1<Kq \leq n.$$ The
corresponding set $A$ consists of the indices $j$, where the
coefficients of $f$ are equal to $1$. Its square
$$f(x)^2=p(x)^2(1+2x^q+\dots+Kx^{(K-1)q}+\dots+2x^{(2K-3)q}+x^{(2K-2)q})
$$ has the coefficients at least $1$ for $x^j$
for $j=0,1,\dots,(2K-1)q-1$.  Using $n < K(q+1)$, we obtain
$$(2K-1)q-1  \geq (2-\eps)K(q+1) > (2-\eps)n \geq \lfloor (2-\eps)n \rfloor,$$
because, by the choice of $K$ and $q_0$,
$$(2K-1)q-1-(2-\eps)K(q+1)= \eps Kq-2K-q+\eps K-1
$$
$$=K(\eps q/2-2)+ q (\eps K/2-1) +\eps K-1 \geq 0+0+\eps (2/\eps)-1=1.$$ It
follows that $A+A$ contains the set $\{0,1,\dots,\lfloor
(2-\eps)n\rfloor\}$. Finally, as $K \geq 2$, we obtain
$$H(f^2) \leq 2KH(p^2)<2Kc \log (2q) \leq 2Kc \log(2n/K) <C \log n$$
with the constant $C:=2Kc$.  This proves
Corollary~\ref{ee55}.

\section{Proof of Theorem~\ref{ee5}}

Fix a positive constant $\eps<1/80$. We shall split the set
$\{2,3,\dots,n\}$ into two sets ${\mathcal S}_1$ and ${\mathcal
S}_2$ depending on whether  for $m \in \{2,3,\dots,n\}$ we have
$T_m \leq \eps^{-3} \log m$ (set ${\mathcal S}_1$) or
$T_m>\eps^{-3} \log m$  (set ${\mathcal S}_2$). Both sets are
nonempty, because, by Lemmas~\ref{l1} and \ref{l2}, for $n$ large
enough
 $\lfloor n/2 \rfloor \in {\mathcal S}_1$ and $n \in {\mathcal S}_2$.

This time, we select
\begin{equation}\label{lambd2}
\lambda:=\sqrt{2}(1+\eps/3),
\end{equation}
so that \eqref{lambd} is satisfied. Let $E_m$, $2 \leq m \leq n$,
be the event that the random variable $V_m$ which is defined in
\eqref{vi11}, \eqref{vi21}, \eqref{vi31} and \eqref{vi311} belongs
to the union of intervals
$$[0, (\eps/4) T_m) \cup (T_m,\infty)  \>\>\>\> \text{in case}\>\>\>\>m \in {\mathcal S}_1,$$
and to the union of intervals
$$[0, (1-\eps/5) T_m) \cup ((1+\eps/5) T_m,\infty)\>\>\>\> \text{in case}\>\>\>\>m \in {\mathcal S}_2.$$

Suppose first that $m \in {\mathcal S}_1$ and that $m$ is large
enough. Then, applying inequality \eqref{down} to the sum of
Bernoulli trials $V_m$ with $\delta:=1-\eps/4$ and using $$T_m
\geq S_m>2(1+2\eps/3)\log m$$ (see Lemma~\ref{l1}, \eqref{111},
\eqref{112}, \eqref{lambd2}),  we obtain
\[\P(V_m<(\eps/4)T_m) \leq e^{-(1-\eps/4)^2 T_m/2} <e^{-(1-\eps/4)^2 (1+2\eps/3)\log m}
< m^{-1-\eps/7},\] because $1+\eps/7<(1-\eps/4)^2(1+2\eps/3)$ for
$0<\eps<0.08$.
 Similarly, applying \eqref{up} with
$\delta:=2$, we derive that
$$\P(V_m>3 T_m) \leq e^{-(3 \log 3 - 2) T_m} < e^{-2 \log m} = m^{-2},$$
since $2/(3\log 3-2)<2<T_m/\log m$. Hence
\begin{equation}\label{wre}
\P(E_m) = \P(V_m \notin [(\eps/4)T_m, 3T_m]) \leq m^{-1-\eps/7}+
m^{-2} \leq 2m^{-1-\eps/7}
\end{equation}
for each sufficiently large $m \in {\mathcal S}_1$.

We next give an upper bound for the event $V_m \notin
[(1-\eps/5)T_m, (1+\eps/5)T_m]$ when $m \in {\mathcal S}_2$ is
large enough. By \eqref{che2}, \eqref{vi41} and $T_m>\eps^{-3}\log
m$, we find that
$$\P(E_m) = \P (|V_m-T_m|>(\eps/5) T_m))=
\P(|V_m-\E(V_m)| >(\eps/5) \E(V_m)) $$ $$\leq 2 e^{-\eps^2
\E(V_m)/75} = 2 e^{-\eps^2 T_m/75}< 2 m^{-1/75\eps}.$$ Therefore,
\begin{equation}\label{wre1}
\P(E_m) = \P(V_m \notin [(1-\eps/5)T_m, (1+\eps/5)T_m]) <
2m^{-1/75\eps} < m^{-1-\eps/7}
\end{equation}
 for each sufficiently large $m \in
{\mathcal S}_2$, because $1/75\eps>1+\eps/7$ for $0<\eps<1/80$.

Observe that, by \eqref{vi31} and \eqref{vi311}, $Z_m-2V_m \in
\{Y_{m/2}, Y_{n-m/2}^*\}$. So the event $E_m$, i.e., $V_m \notin
[(\eps/4)T_m, 3T_m]$ (for $m \in {\mathcal S}_1$) contains the
event $Z_m \notin [(\eps/3)T_m,7T_m]$ for each sufficiently large
$m$. Also, as $m \in {\mathcal S}_1$, we have $2\log m <T_m \leq
\eps^{-3} \log m$, so the latter event contains the event $Z_m
\notin [(\eps/2) \log m, \eps^{-4} \log m]$. Using \eqref{wre} we
obtain
\begin{equation}\label{ne1}
\P(Z_m \notin [(\eps/2) \log m, \eps^{-4} \log m]) \leq
2m^{1-\eps/7}
\end{equation}
for each sufficiently large $m \in {\mathcal S}_1$, $m \leq n$.

Similarly, for $m \in {\mathcal S}_2$ the event $E_m$, i.e., $V_m
\notin [(1-\eps/5)T_m, (1+\eps/5)T_m]$ contains the event $Z_m
\notin [2(1-\eps/4)T_m,2(1+\eps/4)T_m]$ for each sufficiently
large $m$. Note that \[2 \log m < T_m < (1+7\eps/10)(4/\pi) (\log
n)^2,\] by \eqref{112}, \eqref{114}, \eqref{lambd2},  because
$\lambda^2=2(1+2\eps/3+\eps^2/9)<2(1+7\eps/10)$ for $0<\eps<1/4$.
Therefore, from \eqref{wre1} and
$(1+7\eps/10)(1+\eps/4)<1+39\eps/40<1+0.98\eps$ (for $0<\eps<1/7$)
we find that
\begin{equation}\label{ne2}
\P(Z_m \notin [3 \log m, (1+0.98\eps)(4/\pi)(\log n)^2]) <
m^{-1-\eps/7}
\end{equation}
 for each sufficiently large $m \in {\mathcal S}_2$,
$m \leq n$. By \eqref{vi323232}, inequalities \eqref{ne1} and
\eqref{ne2} also hold for $Z_m$ replaced with $Z_{2n-m}$. From
\eqref{ne1} and \eqref{ne2} we derive that there is a positive
integer $M_1$ such that
$$\P(Z_m \notin [(\eps/2) \log m, (1+0.98\eps)(4/\pi)(\log n)^2])
\leq 2m^{-1-\eps/7}$$ for each $m=M_1+1,\dots,n$ and the same
holds for $Z_m$ replaced with $Z_{2n-m}$.

Since
$$\sum_{m=M_1+1}^{2n-M_1-1} 2m^{-1-\eps/7} <
2\sum_{m=M_1+1}^{\infty} m^{-1-\eps/7}< 1/2$$ for $M_1$ large
enough, by \eqref{bor1}, we conclude that there is an integer
$M=M(\eps)$ such that the probability that all the events
$$\eps \log \min(m,2n-m) \leq Z_m \leq (1+0.98\eps) (4/\pi)(\log n)^2$$ from
$m=M$ to $m=n-M$ hold
is positive. Thus there exists a polynomial
$f(x):=\sum_{j=0}^{n} a_j x^j$, where $a_j \in \{0,1\}$,
$a_0=a_1=a_2=a_{n-2}=a_{n-1}=a_{n}=1$, such that the coefficients
$b_m$ of its square $f(x)^2=\sum_{m=0}^{2n} b_m x^m$ satisfy
$$\eps \log m \leq b_m, b_{2n-m} \leq (1+0.98\eps)(4/\pi)(\log
n)^2$$ for $m \geq M \geq 3$ and $m \leq n$. Here, $M$ depends on
$\eps$, but it does not depend on $n$.

As above, to complete the proof of the theorem let us replace the
Newman polynomial $f(x)$ by the Newman polynomial
$$f_1(x):=\sum_{m=0}^{M-1} (x^m+x^{2n-m}) +\sum_{m=M}^{n-M} a_m x^m.$$
The coefficients of its square $f_1(x)^2$ are all integers and
positive numbers, so they are all at least $1$. Since $L(f_1-f)
\leq 2(M-3)$, Lemma~\ref{l3} implies that the largest coefficient
of $f_1(x)^2$ does not exceed
$$H(f^2)+3(2M-6)<(1+0.98\eps)(4/\pi)(\log n)^2+6M<(1+\eps)(4/\pi)(\log n)^2$$
for each sufficiently large integer $n$. This completes the proof
of the theorem.

Note that, by \eqref{ind}, \eqref{vi11}, \eqref{lambd2}, it is
easy to see that the length of the Newman polynomial $f_1$ whose
existence is just established will be close to
\[2\sum_{k=3}^{\lfloor n/2 \rfloor} \lambda \sqrt{\frac{2\log k}{\pi k}} \sim 4(1+\eps/3) \sqrt{\frac{2n\log n}{\pi}}\]
as $n \to \infty$.

\begin{thebibliography}{99}

\bibitem{alon}
{\sc N.~Alon and M.N.~Kolountzakis,}
{\it On a problem of Erd\H{o}s and Tur\'an and some related results,}
J. Number Theory, {\bf 55} (1995), 82--93.

\bibitem{bor} {\sc P.~Borwein, S.~Choi and F.~Chu,} {\it
An old conjecture of Erd\H os-Tur\'an on additive basis,}
Math. Comp., {\bf 75}
(2006), 475--484.

\bibitem{cher}
{\sc H.~Chernoff,} {\it A measure of asymptotic efficiency for
tests of a hypothesis based on the sum of observations,} Ann.
Math. Stat., {\bf 23} (1952), 493--507.

\bibitem{du1} {\sc A.~Dubickas,} {\it
Additive bases of positive integers and related problems,} Uniform
Distribution Theory, {\bf 3} (2) (2008), 81--90.

\bibitem{du2} {\sc A.~Dubickas and G. \v Semetulskis,} {\it
On polynomials with flat squares,} Acta Arith., {\bf 146} (2011),
247--255.

\bibitem{erdo-1} {\sc P.~Erd\H os,} {\it
On a problem of Sidon in additive number theory,} Acta Sci. Math.,
{\bf 15} (1954), 255--259.

\bibitem{erdo} {\sc P.~Erd\H os,} {\it
Some old and new problems on additive and combinatorial number theory,}
Combinatorial Mathematics: Proc. of the Third Intern. Conf. (New York, 1985),
New York Acad. Sci., New York, 1989, pp. 181--186.

\bibitem{et1} {\sc P.~Erd\H os and P.~Tetali,} {\it
Representations of integers as the sum of $k$ terms,} Random
Struct. Algorithms, {\bf 1} (1990), 245--261.

\bibitem{et} {\sc P.~Erd\H os and P.~Tur\'an,} {\it
On a problem of Sidon in additive number theory and some related
problems,}  J. London Math. Soc., {\bf 16}
(1941), 212--215.

\bibitem{fel} {\sc W.~Feller,} {\it
An introduction to probability theory and its applications. I,} J.
Wiley and Sons, 3rd. ed., New York, London, 1968.

\bibitem{ghhp2} {\sc G.~Grekos, L.~Haddad, C.~Helou and J.~Pihko,} {\it
On the Erd\H os-Tur\'an conjecture,} J. Number Theory, {\bf 102}
(2003), 339--352.

\bibitem{helm1}
{\sc M.~Helm,}
{\it Some remarks on the Erd\H{o}s-Tur\'an conjecture,}
Acta Arith., {\bf 63} (1993), 373--378.

\bibitem{helm2}
{\sc M.~Helm,}
{\it A generalization of a theorem of Erd\H{o}s on asymptotic basis of order 2,}
J. Th\'eor. Nombres Bordeaux, {\bf 6} (1994), 9--19.

\bibitem{mot} {\sc R.~Motwani and P.~Raghavan,} {\it
Randomized algorithms,} Cambridge Univ. Press, New York, NY, 1995.

\bibitem{newn}
{\sc D. J.~Newman,}  {\it An $L^1$ extremal problem for polynomials,}
Proc. Amer. Math. Soc.,
{\bf 16} (1965), 1287--1290.

\bibitem{ruzs}
{\sc I.~Ruzsa,} {\it A just basis,} Monatsh. Math., {\bf 109}
(1990), 145--151.

\bibitem{san} {\sc C.~S\'andor,} {\it
A note on a conjecture of Erd\H os-Tur\'an,}
Integers, {\bf 8}
(2008), \#A30, 4~p.

\bibitem{min1}
{\sc M.~Tang,} {\it A note on a result of Ruzsa,} Bull. Austral.
Math. Soc., {\bf 77} (2008), 91--98.

\bibitem{min2}
{\sc M.~Tang,} {\it A note on a result of Ruzsa, II,} Bull.
 Austral. Math. Soc., {\bf 82} (2010), 340--347.

\bibitem{min3}
{\sc M.~Tang and Y. G~ Chen,} {\it A basis of $\Z_m$},
Colloq. Math., {\bf 104} (2006), 99--103.

\end{thebibliography}

\end{document}
