\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 \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 $0p_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 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 \>\>\> \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\>\>\> \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}(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}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) (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) \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} 3 T_m) \leq e^{-(3 \log 3 - 2) T_m} < e^{-2 \log m} = m^{-2},$$ since $2/(3\log 3-2)<2\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