A basis of finite and infinite sets with small representation function (Q426752)

Summary: Let \(A\) be a subset of the set of nonnegative integers \(\mathbb{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ős asserting that there is a basis \(A\) of \(\mathbb{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+\varepsilon)\log n\) for each sufficiently large integer \(n\). Towards a polynomial version of the Erdős-Turán conjecture we prove that for each \(\varepsilon>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+\varepsilon)(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]\).