A Basis of Finite and Infinite Sets with Small Representation Function
Artūras Dubickas · The Electronic Journal of Combinatorics · 2012
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2012
Abstract
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+\epsilon)\log n$ for each sufficiently large integer $n$.
Towards a polynomial version of the Erdős-Turán conjecture we prove that for each $\epsilon>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+\epsilon)(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]$.
Open the resolved locator · 10.37236/13
Metadata licence: OpenAlex metadata (CC0)