×

Generalized additive bases, König’s lemma, and the Erdős–Turán conjecture. (English) Zbl 1090.11010

Let \(A\) be a set of integers, as usual we denote by \(r_A(n,h)\) the number of representations of n as \(n=a_1+a_2+\dots +a_h; \;a_1\leq a_2\leq \dots \leq a_h, a_1,a_2,\dots ,a_h\in A.\) The set \(A\) is said to be a basis of order \(h\) if \(r_A(n,h)>0\) for all nonnegative integers \(n\), and asymptotic basis of order \(h\) if \(r_A(n,h)=0\) for only finitely many positive \(n\).
The author introduced the notion of generalized additive bases. Let \(\mathbf{H}=\{H_n\}_{n=0}^\infty\) be a sequence of nonempty finite sets of positive integers. For a set \(A\) of nonnegative integers define the generalized representation function by \(r_A(n,H_n)=\sum_{h_n\in H_n}r_A(n,h_n).\) Let \(\mathbf{R}=\{R_n\}_{n=0}^\infty\) be a sequence of nonempty finite sets of positive integers. If \(r_A(n,H_n)\in R_n\) for every \(n\geq 0\), then \(A\) is said to be an \(\mathbf{R}\)-basis of order \(\mathbf{H}\). In the present paper the author investigates the generalized representation problem and proves:
Theorem 1. Let \(\mathbf{H}=\{H_n\}_{n=0}^\infty\) be a sequence of nonempty finite sets of positive integers. There exists a finite set \(A\) that is a basis of order \(\mathbf{H}\) or an asymptotic basis of order \(\mathbf{H}\) if and only if \(\liminf_{n\rightarrow \infty} max(H_n)/n>0.\)
Theorem 2. Let \(\mathbf{R}=\{R_n\}_{n=0}^\infty\) and \(\mathbf{H}=\{H_n\}_{n=0}^\infty\) be sequences of nonempty finite sets of positive integers such that \(\lim_{n\rightarrow \infty}\max(H_n)/n=0.\) There exists an \(\mathbf{R}\)-basis of order \(\mathbf{H}\) if and only if for every \(N\) there exists a finite \(\mathbf{R}\)-basis \(A_N\) of order \(\mathbf{H}\) with \(\max(H_N)\geq N.\)
Using the second result a result of Dowd is derived, which is related to the celebrated conjecture of Erdős and Turán: Let \(c\geq 1\) and \(h\geq 2\). There exists a basis \(A\) of order \(h\) such that \(r_A(n,h)\leq c\) for all \(n\geq 0\) if and only if , for every \(N\), there exists a finite set \(A_N\) of natural numbers such that \(\max(A_N)\geq N\) and \(1\leq r_{A_N}(n,h)\leq c\) for all \(n=0,1,\dots , \max(A_N).\) The main tool of the proofs is the (graph theoretical) König’s lemma.

MSC:

11B13 Additive bases, including sumsets
11B05 Density, gaps, topology
11B34 Representation functions

References:

[1] Dowd, M., Questions related to the Erdős-Turán conjecture, SIAM J. Discrete Math., 1, 142-150 (1988) · Zbl 0645.94011
[2] Erdős, P.; Turán, P., On a problem of Sidon in additive number theory and some related questions, J. London Math. Soc., 16, 212-215 (1941) · Zbl 0061.07301
[3] Grekos, G.; Haddad, L.; Helou, C.; Pihko, J., On the Erdős-Turán conjecture, J. Number Theory, 102, 339-352 (2003) · Zbl 1083.11010
[4] Nathanson, M. B., Representation functions of sequences in additive number theory, Proc. Amer. Math. Soc., 72, 16-20 (1978) · Zbl 0396.10045
[5] M.B. Nathanson, Every function is the representation function of an additive basis for the integers, arXiv: math.NT/0302091. Port. Math., to appear.; M.B. Nathanson, Every function is the representation function of an additive basis for the integers, arXiv: math.NT/0302091. Port. Math., to appear.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.