Generalized additive bases, König's lemma, and the Erdős--Turán conjecture (Q1434336)

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.