Higher degree Erdős distinct evaluations problem

EUROCOMB’23

Simone Costa Stefano Della Fiore Andrea Ferraguti

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-043

PDF
Abstract
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}}.$$

Pages:
314–319
References

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.
https://doi.org/10.1016/j.ejc.2023.103712

I. Aliev, Siegel's lemma and sum-distinct sets, Discrete Comput. Geom. 39 (2008), 59-66.
https://doi.org/10.1007/s00454-008-9059-9

J. Bae, On subset-sum-distinct sequences. Analytic number theory, Vol. 1, Progr. Math., 138, Birkhauser, Boston (1996), 31-37.
https://doi.org/10.1007/978-1-4612-4086-0_3

T. Bohman, A construction for sets of integers with distinct subset sums, Electron. J. Combin. 5 (1998), Research Paper 3, 14 pages.
https://doi.org/10.37236/1341

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.
https://doi.org/10.1016/j.dam.2022.10.015

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.
https://doi.org/10.1016/0097-3165(86)90116-0

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.
https://doi.org/10.1137/20M1385883

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).
https://doi.org/10.1016/S0304-0208(08)73500-X

R. K. Guy, Unsolved Problems in Intuitive Mathematics, Vol. I, Number Theory, Problem C8, Springer-Verlag (1981).
https://doi.org/10.1007/978-1-4757-1738-9

W.F. Lunnon, Integer sets with distinct subset sums, Math. Compute, 50 (1988) 297-320.
https://doi.org/10.1090/S0025-5718-1988-0917837-5

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Simone Costa, Stefano Della Fiore, Andrea Ferraguti

PDF