Top

Foundations of Computational Mathematics

Published in:

01-12-2016

Structural Approach to Subset Sum Problems

Author: Endre Szemerédi

Published in: Foundations of Computational Mathematics | Issue 6/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We discuss results obtained jointly with Van Vu on the length of arithmetic progressions in $\ell $-fold sumsets of the form

$$\begin{aligned} \ell \mathcal {A}=\{a_1+\dots +a_\ell ~|~a_i\in \mathcal {A}\} \end{aligned}$$

and

$$\begin{aligned} \ell \mathcal {A}=\{a_1+\dots +a_\ell ~|~a_i\in \mathcal {A}\text { all distinct}\}, \end{aligned}$$

where $\mathcal {A}$ is a set of integers. Applications are also discussed.

previous article Do Orthogonal Polynomials Dream of Symmetric Curves?

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Andrews, G.E.: The theory of partitions. Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam (1976). Encyclopedia of Mathematics and its Applications, Vol. 2

Bilu, Y.: Structure of sets with small sumset. Astérisque (258), xi, 77–108 (1999). Structure theory of set addition

Bourgain, J.: On arithmetic progressions in sums of sets of integers. In: A tribute to Paul Erdős, pp. 105–109. Cambridge Univ. Press, Cambridge (1990)

Cassels, J.W.S.: On the representation of integers as the sums of distinct summands taken from a fixed set. Acta Sci. Math. Szeged 21, 111–124 (1960)MathSciNetMATH

Chen, Y.G.: On subset sums of a fixed set. Acta Arith. 106(3), 207–211 (2003). doi:10.4064/aa106-3-1.

Croot, E., Ruzsa, I., Schoen, T.: Arithmetic progressions in sparse sumsets. In: Combinatorial number theory, pp. 157–164. de Gruyter, Berlin (2007)

Davenport, H.: On the addition of residue classes. J. Lond. Math. Soc. 10, 30–32 (1935). doi:10.1112/jlms/s1-10.37.30 MATH

Dias da Silva, J.A., Hamidoune, Y.O.: Cyclic spaces for Grassmann derivatives and additive theory. Bull. London Math. Soc. 26(2), 140–146 (1994). doi:10.1112/blms/26.2.140.

Erdős, P.: On the representation of large integers as sums of distinct summands taken from a fixed set. Acta Arith. 7, 345–354 (1961/1962)

10.

Erdős, P., Heilbronn, H.: On the addition of residue classes mod p. Acta Arith. 9, 149–159 (1964)

11.

Folkman, J.: On the representation of integers as sums of distinct terms from a fixed sequence. Canad. J. Math. 18, 643–655 (1966)MathSciNetCrossRefMATH

12.

Freiman, G.A., Halberstam, H., Ruzsa, I.Z.: Integer sum sets containing long arithmetic progressions. J. London Math. Soc. (2) 46(2), 193–201 (1992). doi:10.1112/jlms/s2-46.2.193.

13.

Freĭman, G.A.: Foundations of a structural theory of set addition. American Mathematical Society, Providence, R. I. (1973). Translated from the Russian, Translations of Mathematical Monographs, Vol 37

14.

Green, B.: Arithmetic progressions in sumsets. Geom. Funct. Anal. 12(3), 584–597 (2002). doi:10.1007/s00039-002-8258-4.

15.

Griffiths, S.: Asymptotically tight bounds on subset sums. Acta Arith. 138(1), 53–72 (2009). doi:10.4064/aa138-1-3.

16.

Hamidoune, Y.O., Lladó, A.S., Serra, O.: On complete subsets of the cyclic group. J. Combin. Theory Ser. A 115(7), 1279–1285 (2008). doi:10.1016/j.jcta.2007.12.007.

17.

Hegyvári, N.: On the representation of integers as sums of distinct terms from a fixed set. Acta Arith. 92(2), 99–104 (2000)MathSciNetMATH

18.

Łuczak, T., Schoen, T.: On the maximal density of sum-free sets. Acta Arith. 95(3), 225–229 (2000)MathSciNetMATH

19.

Olson, J.E.: Sums of sets of group elements. Acta Arith. 28(2), 147–156 (1975/76)

20.

Olson, J.E.: An addition theorem modulo $p$. J. Combinatorial Theory 5, 45–52 (1968)MathSciNetCrossRefMATH

21.

Ruzsa, I.Z.: Generalized arithmetical progressions and sumsets. Acta Math. Hungar. 65(4), 379–388 (1994). doi:10.1007/BF01876039.

22.

Ruzsa, I.Z.: Arithmetic progressions in sumsets. Acta Arith. 60(2), 191–202 (1991)MathSciNetMATH

23.

Sárközy, A.: Finite addition theorems. I. J. Number Theory 32(1), 114–130 (1989). doi:10.1016/0022-314X(89)90102-9.

24.

Szemerédi, E., Vu, V.H.: Finite and infinite arithmetic progressions in sumsets. Ann. of Math. (2) 163(1), 1–35 (2006). doi:10.4007/annals.2006.163.1.

25.

Szemerédi, E., Vu, V.H.: Long arithmetic progressions in sum-sets and the number of $x$-sum-free sets. Proc. London Math. Soc. (3) 90(2), 273–296 (2005). doi:10.1112/S0024611504015059.

26.

Szemerédi, E., Vu, V.H.: Long arithmetic progressions in sumsets: thresholds and bounds. J. Amer. Math. Soc. 19(1), 119–169 (2006). doi:10.1090/S0894-0347-05-00502-3.

27.

Vu, V.H.: Some new results on subset sums. J. Number Theory 124(1), 229–233 (2007). doi:10.1016/j.jnt.2006.08.012.

Title: Structural Approach to Subset Sum Problems
Author: Endre Szemerédi
Publication date: 01-12-2016
Publisher: Springer US
Published in: Foundations of Computational Mathematics / Issue 6/2016
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-016-9326-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 6/2016

Condition Length and Complexity for the Solution of Polynomial Systems

Do Orthogonal Polynomials Dream of Symmetric Curves?

Application of Quasi-Monte Carlo Methods to Elliptic PDEs with Random Diffusion Coefficients: A Survey of Analysis and Implementation

The L-Functions and Modular Forms Database Project

Preface

Multi-index Stochastic Collocation Convergence Rates for Random PDEs with Parametric Regularity

Premium Partner