Higher degree Erdős distinct evaluations problem


Let $\Sigma=\{a_1, . . . , a_n\}$ be a set of positive integers with $a_1 < \dots < a_n$ such that all $2^n$ subset sums are distinct. A famous conjecture by Erdős states that $a_n>c\cdot 2^n$ for some constant $c$, while the best result known to date is of the form $a_n>c\cdot 2^n/\sqrt{n}$. In this paper, we propose a generalization of the Erdős distinct sum problem that is in the same spirit as those of the Davenport and the Erdős-Ginzburg-Ziv constants recently introduced in \cite{CGS} and in \cite{CS}. More precisely, we require that the non-zero evaluations of the $m$-th degree symmetric polynomial are all distinct over the sub-sequences of $\Sigma$. Even though these evaluations can not be seen as the values assumed by the sum of independent random variables, surprisingly, the variance method works to provide a nontrivial lower bound on $a_n$. Indeed, the main result here presented is to show that $$a_n>c_m\cdot 2^{\frac{n}{m}}/n^{1-\frac{1}{2m}}.$$


N. Alon and J. H. Spencer, The probabilistic method, 4th ed. Wiley, Hoboken, NJ, 2016.

M. Axenovich, Y. Caro, R. Yuster, Sum-distinguishing number of sparse hypergraphs, European Journal of Combinatorics 112 (2023), 103712.

I. Aliev, Siegel's lemma and sum-distinct sets, Discrete Comput. Geom. 39 (2008), 59-66.

J. Bae, On subset-sum-distinct sequences. Analytic number theory, Vol. 1, Progr. Math., 138, Birkhauser, Boston (1996), 31-37.

T. Bohman, A construction for sets of integers with distinct subset sums, Electron. J. Combin. 5 (1998), Research Paper 3, 14 pages.

Y. Caro and J.R. Schmitt. Higher degree Erdős-Ginzburg-Ziv constants, Integers 22 (2022).

Y. Caro, B. Girard and J.R. Schmitt. Higher degree Davenport constants over finite commutative rings, Integers 21 (2021).

S. Costa, S. Della Fiore, M. Dalai: Variation on the Erdős distinct-sums problem. Discrete Applied Mathematics, 325 (2023), 172--185.

N. D. Elkies, An improved lower bound on the greatest element of a sum-distinct set of fixed order, J. Combin. Theory Ser. A 41 (1986), 89-94.

P. Erdős, Problems and results in additive number theory, Colloque sur la Theorie des Nombres, Bruxelles (1955), 127-137.

Quentin Dubroff, Jacob Fox and Max Wenqiang Xu, A note on the Erdős distinct subset sums problem, SIAM J. Discret. Math. 35 (2021), 322-324.

R. K. Guy, Sets of integers whose subsets have distinct sums, Theory and practice of combinatorics, 141-154, North-Holland Math. Stud., 60, Ann. Discrete Math., 12, North-Holland, Amsterdam, (1982).

R. K. Guy, Unsolved Problems in Intuitive Mathematics, Vol. I, Number Theory, Problem C8, Springer-Verlag (1981).

W.F. Lunnon, Integer sets with distinct subset sums, Math. Compute, 50 (1988) 297-320.





PDF views