Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Sumsets and Arithmetic Progressions

ackelsberg_2026_inverse_theorem_sumsets_sets_positive_density/: Characterizes the pairs of positive-density integer sets whose sumset density is exactly the sum of their densities.

adamczewski_2026_erdos1/: Gives the cyclic-matrix and lattice construction disproving the uniform exponential lower bound in Erdős Problem 1.

adenwalla_2022_avoiding_monotone_arithmetic_progressions_permutations_integers/: Constructs a permutation of the integers with no monotone 5-term arithmetic progression and improves several related density bounds.

adenwalla_2023_generalisation_result_monotone_arithmetic_progressions_permutations/: Builds, for every k >= 1, a permutation of the positive integers with no monotone 4-term arithmetic progression whose common difference is not divisible by 2^k.

agrawal_et_al_2025_more_sum_product_problem_integers_few_prime_factors/: Proves stronger sum-product growth for rational sets whose elements have few prime divisors, using low-rank multiplicative covers, S-unit bounds, and higher additive energies.

alon_1989_ascending_waves/: Proves that the two-color ascending-wave number f(k) has order k^3, settling a question of Brown, Erdős and Freedman, and that the longest ascending wave guaranteed in every subset of 1 to n with at least n/2 elements has length between order log^2 n / log log n and order log^2 n.

alon_1990_sum_free_subsets/: Proves that any n nonzero integers contain a sum-free subset of more than n/3 elements, sharpening Erdős's n/3 by a strict inequality, shows the constant cannot exceed 12/29, and determines the sharp constant 2/7 for sum-free subsets of sets in finite Abelian groups.

alon_1995_adding_distinct_congruence_classes_modulo_prime/: Proves the Erdős–Heilbronn conjecture, that the sums of two distinct elements of a k-element subset of the integers modulo a prime p fill at least min(p, 2k-3) residue classes, by an elementary polynomial method, deriving it from the bound min(p, k+l-2) for two sets of different sizes; a short reproof of the Dias da Silva–Hamidoune theorem.

alon_1996_polynomial_method_restricted_sums_congruence_classes/: Alon, Nathanson and Ruzsa's 1996 general polynomial method for sums of congruence classes modulo a prime: Theorem 2.1, a coefficient criterion for the size of a restricted sumset, with the sharp bound of Theorem 3.2 for sums of one element from each of k+1 sets with all summands distinct, the Dias da Silva–Hamidoune theorem |s^A| ≥ min(p, s|A| - s^2 + 1) as its Theorem 3.3, and the Erdős–Heilbronn bound min(p, 2|A| - 3) as the case s = 2 (Theorem 1.3).

alon_2009_discrete_kakeya_type_problems_small_bases/: Constructs small k-universal sets in finite groups and uses them to resolve the Erdős–Newman small-bases question: in a large cyclic group, or any group with a moderately large non-doubling set, every set of at most sqrt(n) elements lies in B B for a set B of size at most 50 sqrt(n) log log n / log n.

alon_2020_sums_products_ratios_along_edges_graph/: Refutes the strong graph form of the Erdos-Szemeredi sum-product conjecture and gives bounds for sums, products and ratios along graph edges.

alon_2025_random_cayley_graphs_random_sumsets/: Shows every small-doubling sumset contains a dense structured set from a short list, improving bounds for random Cayley graphs and non-sumsets.

anderson_2016_vectors_matroids_over_tracts/: Axiomatizes the vectors and covectors of strong matroids over tracts, shows they recover subspaces over fields, unions of cocircuits for ordinary matroids and signed vectors for oriented matroids, and gives phase hyperfield examples where duality, deletion and contraction properties fail.

ardal_2011_chaotic_orderings_rationals_reals/: Constructs linear orderings of the integers, the rationals and the reals with no monotone three-term arithmetic progression, answering the Erdős–Graham question of problem 194 in the negative, and for each k at least 2 an ordering of the reals with monotone k-term but no (k+1)-term progressions.

bae_2026_resolution_erdos_problem_190_via_erdos/: Claims that the canonical Ramsey function satisfies H(k) to the power 1/k divided by k tending to infinity, with a lower bound of order k over log k.

bakkaoui_2026_dissociated_interval_counterexample/: Gives a 13-element positive integer set whose largest dissociated subset has size four, whereas the initial interval of length 13 admits five.

balog_wooley_2015_low_energy_decomposition_theorem/: Decomposes every finite real set into a part of low additive energy and a part of low multiplicative energy, bounds the best exponent for such decompositions by an integer GP-times-progression example that later motivates the BSSZ construction, and adds finite-field and k-fold versions.

balogh_2015_number_maximal_sum_free_subsets_integers/: Proves that the number of maximal sum-free subsets of the first n integers is 2^((1/4+o(1))n), matching the Cameron-Erdos lower bound.

balogh_2018_sharp_bound_number_maximal_sum_free_subsets_integers/: Determines the number of maximal sum-free subsets of the first n integers exactly, as (C_i + o(1))2^{n/4} with the constant depending on n mod 4.

baltz_2000_probabilistic_construction_small_strongly_sum_free/: Randomized arguments using large Sidon sets improve Choi's bounds for strongly sum-free sets, giving g(n) = O(n^(2/5) log^(2/5) n).

basit_2019_improved_sum_product_bound_quaternions/: Proves that every finite set A of quaternions has |A + A| + |AA| >> |A|^(4/3 + c) for an absolute constant c > 0.

baumgartner_1975_partitioning_vector_spaces/: Baumgartner constructs a progression-hitting, three-term-progression-free subset of every rational vector space, which answers Problem 199 negatively.

bedert_2023_unique_sums_abelian_groups/: Records Bedert's compression bound for subset-sum spans in terms of additive dimension and explains its quantitative limitation for Problem 963.

bedert_2024_graham_s_rearrangement_conjecture_beyond_rectification/: Proves Graham's rearrangement conjecture for subsets of the nonzero residues mod p of quasi-polynomial size, far beyond the previous logarithmic bound.

bedert_2025_graham_s_rearrangement_conjecture_over/: Settles the finite-field-model form of Graham's rearrangement conjecture: every subset of F_2^n minus zero of at least constant size has a valid ordering.

bedert_2025_large_sum_free_subsets_sets_integers/: Proves that every set of n integers contains a sum-free subset of size at least n/3 plus a constant times log log n, the first unbounded improvement of Erdős's n/3, with a structure theorem for sets whose largest sum-free subset is n/3 plus a constant.

beker_2025_erdos_moser_sum_free_set_problem/: Improves the bounds for sets lacking k-configurations and gives a new proof of the best-shape lower bound for the Erdős-Moser sum-free set problem.

berlekamp_1968_construction_partitions_which_avoid_long_arithmetic/: Gives a Galois-field construction of colorings without long progressions, yielding the lower bound W(2,t) greater than t times 2 to the t for prime t.

blanco_santos_2014_lattice_3_polytopes_few_lattice_points/: Classifies three-dimensional lattice polytopes with five lattice points up to unimodular equivalence and proves that for each size there are finitely many classes of width greater than one.

bloom_2020_breaking_logarithmic_barrier_roth_s_theorem/: Shows that a subset of {1,...,N} with no non-trivial three-term arithmetic progression has size << N/(log N)^(1+c) for an absolute constant c > 0.

bloom_2023_improvement_kelley_meka_bounds_three_term/: Sharpens the Kelley-Meka bound so a progression-free subset of the first N integers has density at most exp of minus a ninth power of log N.

bloom_2026_sidon_complement_constructions/: Collects three supplied counterexample methods and separates their proofs from historical and formal claims.

bloom_2026_sum_product_conjecture_is_false_real/: Disproves the sum-product conjecture over the reals by building large sets of algebraic integers whose sumset and product set both stay small.

bode_harborth_2005_directed_paths_diagonals_within_polygons/: Bode and Harborth's 2005 proof of the two largest cases of Alspach's conjecture on directed paths of diagonals within an n-gon, that is, on orderings of a subset of Z_n minus {0} with nonzero sum whose partial sums are distinct and nonzero: Theorem 1, the case of all n - 1 lengths (whose sum is nonzero only for even n), and Theorem 2, the case of n - 2 lengths for every n, the source of the size p - 2 in the near-full range of Problem 475.

bohman_1997_construction_sets_integers_distinct_subset_sums/: Source record and research digest.

bosznay_1989_lower_estimation_non_averaging_sets/: Bosznay's 1989 three-page note proving that the largest non-averaging subset of the first n integers has more than c n^{1/4} elements for all large n: the numbers i q^3 + i(i+1)/2 for i = 1, ..., q-1 form a non-averaging set below 2q^4, because the points (iq, i(i+1)/2) lie on a parabola; the matching lower bound to the n^{1/4+o(1)} upper bound of Problem 186, and the alpha = 1/4 input to the N^{1/5} bound of Problem 131.

bourgain_1997_estimates_related_sumfree_subsets_sets_integers/: Bourgain's 1997 harmonic-analysis paper on sum-free subsets: Proposition 1.3, every set B of at least three positive integers has a sum-free subset of size at least (|B| + 2)/3 (the printed statement omits the size condition, which B = {1, 2} shows is needed), the bound after Erdős's |B|/3 and Alon and Kleitman's (|B| + 1)/3; Proposition 1.4, the excess over |B|/3 is at least a constant times the L^1 norm of the cosine sum over B divided by log |B|; Proposition 1.7, a log |B| / log log |B| gain for 3-sum-free subsets; and the fact that the k-sum-free constant tends to 0.

bourgain_chang_2009_sum_product_theorems_algebraic_number_fields/: Develops a fixed-degree algebraic-number version of the few-products, many-sums principle and isolates the degree barrier escaped by later real counterexamples.

brown_1990_quasi_progressions_descending_waves/: Relates progressions, quasi-progressions, cubes and descending waves, and bounds the two-coloring number for k-term descending waves.

candela_helfgott_2014_dimension_additive_sets/: Candela and Helfgott compare four notions of additive dimension, including the maximum and lower dissociativity dimensions relevant to Problem 963.

chang_2003_erdos_szemeredi_problem_sum_set_product_set/: Shows that a finite set of positive integers with a small product set has a nearly maximal sum set, and pins down the growth of the least number of simple sums plus simple products of k positive integers.

chen_2015_conjecture_sarkozy_szemeredi/: Disproves a conjecture of Sarkozy and Szemeredi by showing that for additive complements with lim sup A(x)B(x)/x <= 1 the excess A(x)B(x) - x eventually exceeds every power of the smaller counting function.

choi_1974_extremal_problem_number_theory/: Choi's 1974 lower bound for h(n), the largest size guaranteed for a subset of any n nonzero integers in which two sums of elements are equal only when they have equally many summands: the estimate (1), h(n) >> n^(1/3) (log n)^(1/3), sharpening Erdős's n^(1/3), by a p-adic decomposition of the set and a lemma extracting >> log K integers from K residue classes with distinct subset sums modulo p.

choi_1975_additive_multiplicative_problems_number_theory/: Determines how many integers with all pairwise sums inside a dense set can be found, and gives probabilistic multiplicative analogs.

choi_1975_sum_free_subsequences/: Proves the largest guaranteed sum-free subset of n distinct integers has size between roughly the square root of n log n over log log n and n over log n.

cipollini_2026_sharp_5_8_bound_erdos_sos/: Proves every subset of 1..N of size at least 5N/8+O(1) contains a pairwise-sum triple, settling the sharp constant.

conlon_2023_homogeneous_structures_subset_sums_non_averaging/: Finds homogeneous generalized progressions inside subset sums, giving the first polynomial gain on the Erdos-Straus non-averaging problem.

coppersmith_phillips_1996_question_erdos_subsequence_sums/: Coppersmith and Phillips's 1996 note on Erdős's question how many integers in [1,n] can avoid being a sum of consecutive members: Theorem 2.1, a sequence of 13n/24 − O(1) such integers, improving Freud's 19n/36, and Theorem 3.7, the upper bound 2n/3 − ⌊n/512⌋ + 3 log_4 n − 1/2, so the maximal density lies in [13/24, 2/3 − 1/512].

costa_2020_new_results_about_conjecture_brian_alspach/: Proves Alspach's partial-sums conjecture for subsets of size at most 11 of every torsion-free abelian group, gives an asymptotic result in cyclic groups, and proves Graham's distinct-partial-sums variant for subsets of size at most 12 of cyclic groups of prime order.

costa_2026_new_bounds_weak_sequenceability/: Improves the size bound for which Graham's sequenceability conjecture holds in cyclic groups from exp(c(log p)^(1/4)) to exp(c(log p)^(1/3)).

costa_et_al_2021_variations_erdos_distinct_sums_problem/: Studies bounded integer and vector sequences whose restricted subset sums are distinct, with quantitative lower bounds and constructions.

cushman_2025_note_sum_product_problem_convex_sumset/: Records Cushman's real sum-product lower bound, which also applies to the integer setting of Erdős Problem 52, and the popular-set refinement behind it.

dadderio_moci_2011_arithmetic_matroids_tutte_polynomial_toric_arrangements/: Introduces arithmetic matroids, matroids with a multiplicity function whose prototype is a list in a finitely generated abelian group, proves that the dual of a representable one is representable, and gives a Crapo-type combinatorial interpretation of the arithmetic Tutte polynomial.

dash_et_al_2016_continuous_knapsack_set/: Bounds distinct coefficients in mixed-integer knapsack facets using empty projected lattice polytopes and develops the low-integer-variable cases.

davis_nd_permutations_containing_no_long_arithmetic_progressions/: Bounds the number of permutations of one to n with no monotone three-term arithmetic progression and treats singly and doubly infinite permutations.

deshouillers_1995_additive_problem_erdos_straus/: Deshouillers and Freiman's 1995 bound card A ≤ 2N^{1/2} + C N^{5/12} for an admissible subset A of [1,N], the (2+o(1))√N bound with the constant Straus showed to be best possible, and the structure theorem for admissible sets with more than 1.96√N elements on which their 1999 exact bound rests.

deshouillers_1999_additive_problem_erdos_straus/: Proves Erdos's conjectured maximum size for an admissible subset of the first N integers, for all sufficiently large N.

dias_da_silva_hamidoune_1994_cyclic_spaces_grassmann_derivatives_additive_theory/: Dias da Silva and Hamidoune's 1994 proof of the Erdős–Heilbronn conjecture and of its m-fold form: the sums of the m-subsets of a finite subset A of a field of characteristic p number at least min(p, m|A| - m^2 + 1) (Theorem 4.1), from a lower bound for the dimension of a cyclic subspace of the derivative of a linear operator on the mth Grassmann space; also lowers Olson's subset-sum threshold in Z_p to [sqrt(4p - 7)] + 1 (Theorem 4.2), or [sqrt(4p - 7)] for sets avoiding zero (Corollary 4.3).

doorn_2026_cardinality_set_containing_pairwise_sums_fixed/: Determines the Choi-Erdos-Szemeredi thresholds exactly for three and four integers and bounds the five-integer one by a constant.

dubroff_2021_note_erdos_distinct_subset_sums_problem/: Gives two short proofs of the best known lower bound on the largest element of a set of n positive integers with all subset sums distinct.

duval_et_al_2012_cuts_flows_cell_complexes/: Extends graph cuts and flows to finite cell complexes: bases of the cut and flow spaces with torsion coefficients as entries, integral bases under torsion conditions, the critical and cocritical groups as discriminant groups of the cut and flow lattices, their orders, and Hermite-constant bounds for girth and connectivity.

eberhard_2014_sets_integers_no_large_sum_free/: Answers a 1965 question of Erdos by constructing sets of n integers whose largest sum-free subset has only about a third of n elements.

edmonds_1965_minimum_partition_matroid_into_independent_subsets/: A focused E0774 digest of the complete paper.

erdos_1948_representation_1/: States that the least size of a restricted difference basis for the integers up to n, divided by the square root of n, tends to a limit lying between sqrt(2 + 4/(3π)) and sqrt(8/3).

erdos_1956_problems_results_additive_number_theory/: A lecture surveying additive problems open to probabilistic methods: representation functions and the Erdos-Turan conjecture, thin bases and additive complements, Schnirelmann density and essential components, and the Erdos-Moser problem on sets with distinct subset sums.

erdos_1957_unsolved_problems/: A lecture list of open problems in number theory, geometry and analysis, with references and further questions added by the author.

erdos_1962_szamelmeleti_megjegyzesek/: Shows sum-free integer sequences have density zero, with growth bounds, and bounds sets whose subset sums determine the number of summands.

erdos_1965_extremal_problems_number_theory/: Survey of extremal number-theory problems that also proves bounds on subset sums with distinct summands and on sum-free selection from n reals.

erdos_1973_problems_results_combinatorial_number_theory/: Survey of combinatorial number theory that records square-root bounds for sum-free selection and reports difficulty in reconstructing the proof of the claim l(n) = o(n) printed in 1965.

erdos_1975_problems_results_combinatorial_number_theory/: Survey of problems around van der Waerden's theorem, Szemeredi's regularity lemma, sum-free sequences and infinite coloring questions.

erdos_1979_old_new_problems_results_combinatorial_number/: A survey chapter collecting problems and results around van der Waerden's theorem, arithmetic progressions and related combinatorial number theory.

erdos_1980_applications_ramsey_s_theorem_additive_number/: Ramsey's theorem yields a Sidon-type sequence that cannot be split into finitely many Sidon sequences, plus upper bounds on extractable Sidon subsets.

erdos_1983_sums_products_integers/: Proves a sum-product bound: any n positive integers give more than n to the power one plus a constant sums and products.

erdos_1991_sommes_de_sous_ensembles/: Improves the upper bound for the largest set in the first N integers whose subset sums determine the subset size, and builds an infinite such set.

erdos_freud_1984_disjoint_sets_differences/: Erdős and Freud's 1984 study of pairs of integer sequences A, B for which a_i − a_j = b_k − b_l has only trivial solutions: the binary-digit counterexample to the Erdős–Graham question of Problem 331, with liminf min{A(x), B(x)}/√x = 1/√2, the generalized number-system construction, Theorems 1–3 on the limits of A(x)B(x)/x and of min{A(x), B(x)}/√x and max{A(x), B(x)}/√x, and Theorem 4, that when liminf min{A(x), B(x)}/√x > 0 neither A(x)/√x nor B(x)/√x tends to a limit.

erdos_problems_2026_problem_963_discussion/: Source record and research digest.

erdos_sarkozy_1992_arithmetic_progressions_subset_sums/: Erdős and Sárközy's 1992 study of arithmetic progressions among the subset sums of a t-element subset of {1, ..., N} when t is small against root N: the thresholds F(N,t) and G(N,t) for consecutive multiples and for progressions, and for three terms the bounds [log N/log 3] + 2 ≤ K(N) < (log N + log log N)/log 3 + 2 (Theorem 4) and the companion bound on L(N) (Theorem 5); the source of the bound g_3(n) ≫ 3^n / n^{O(1)} on Problem 817.

erdos_sos_1986_problems_results_intersections_set_systems_structural_type/: Sets up strong and weak structural-intersection problems, records the arithmetic-progression conjecture behind Problem 272, quotes the partition/Hamming-distance lemma, and describes the kernel-system viewpoint used for weak intersection families.

fox_2019_sets_without_term_progressions_can_have/: Shows a set of n integers free of k-term progressions can still contain almost n squared shorter progressions, answering a question of Erdős.

fox_2026_three_color_van_der_waerden_numbers/: Proves the three-color van der Waerden numbers grow faster than any exponential, and gives new multicolor lower bounds.

frankl_furedi_1986_non_trivial_intersecting_families/: Source record and research digest.

freud_1993_adding_numbers_problem_p/: Constructs sets in [1,n] of size 19n/36+O(1) in which no element is a sum of consecutive elements, and records, without proof, that the density is at most 2/3.

geneson_2019_forbidden_arithmetic_progressions_permutations_subsets_integers/: Constructs a permutation of the integers with no monotone six-term arithmetic progression, improving the seven of Davis, Entringer, Graham and Simmons, and bounds the densities of sets of integers that can be permuted to avoid short progressions.

georgiev_2025_mathematical_exploration_discovery_at_scale/: Applies the AlphaEvolve evolutionary coding agent to 67 open problems, matching known records and improving several bounds.

gordon_1962_determination_sets_sets_sums_certain_order/: Shows that distinct multisets rarely share the same multiset of s-fold sums, with F_s(n)=1 for all but finitely many n when s>2.

graham_1977_extremal_density_theorems_linear_forms/: Introduces the critical density of a system of linear forms, proves the density 1 minus 1/n for augmented arithmetic progressions, derives a series formula for the largest density of a set with no triple n, 2n, 3n, and asks whether that density is irrational, the question of problem 168.

graham_et_al_1980_note_intersection_properties_subsets_integers/: Shows that distinct subsets of {1,...,n} whose pairwise intersections are arithmetic progressions, possibly empty, number at most C(n,3)+C(n,2)+n+1, attained only by all sets of at most three elements; solves the interval analogues and announces an upper bound c n^2 when intersections must be nonempty.

green_2008_primes_contain_arbitrarily_long_arithmetic_progressions/: Proves the primes contain arithmetic progressions of every length, and more generally that any subset of the primes of positive relative upper density does.

green_2017_new_bounds_szemeredi_s_theorem/: Proves that sets of integers up to N with no four-term arithmetic progression have size at most a constant times N(log N)^{-c}, for an absolute constant c > 0.

grosswald_1982_arithmetic_progressions_that_consist_only_primes/: Proves an asymptotic series for the number of three-term arithmetic progressions of primes up to x, and derives the m-term asymptotic from a strong form of the prime k-tuple conjecture.

hanson_et_al_2023_sum_product_problem_integers_few_prime_factors/: Source record and research digest.

haugland_1996_advances_minimum_overlap_problem/: Proves the minimum overlap limit exists, reproduces Swinnerton-Dyer's proof that fractional step profiles are approximable by balanced binary ones, and bounds Problem 36's constant above by 0.382003 from a 21-step candidate.

haugland_2016_minimum_overlap_problem_revisited/: Gives a step function lowering the known upper bound for Erdos's minimum overlap constant to about 0.380927.

hegyvari_1986_consecutive_sums_sequences/: Hegyvári's 1986 paper on consecutive sums (c-sums) of finite integer sequences: Theorem 1, the largest number f(n) of integers in [1, n] with all c-sums distinct satisfies (1/3 + o(1))n ≤ f(n) ≤ (2/3 + o(1))n, answering Erdős and Harzheim; Theorem 3, an increasing sequence starting at a with gaps at most K and all c-sums distinct ends below (a + K/2)e^(K+1) + Ke^(2K+2); with Theorems 2 and 4 on translates of {1, ..., k} and on difference sets with increasing gaps.

hicks_2019_distinct_partial_sums_cyclic_groups_polynomial/: Proves Alspach's distinct-partial-sums conjecture for prime n when the subset has at most 10 elements or exactly n-3 elements (the sizes n-1 and n-2 being Bode and Harborth's).

hosten_maclagan_2000_vertex_ideal_lattice/: Encodes vertices of integer lattice fibers in a monomial ideal and bounds associated-prime codimension in terms of lattice rank.

huang_2026_autonomous_disproofs_sum_product_real/: Reports a GPT-5.5 Pro agent that reproved the known real-number disproof of the sum-product conjecture in seven of eight trials; holds the Zenodo deposit, not the arXiv edition, with explicit verification limits.

hunter_2025_lower_bounds_multicolor_van_der_waerden/: Gives an exponential improvement to lower bounds for diagonal van der Waerden numbers with at least five colors via a randomized blow-up construction.

jenw1n_2026_erdos_problem_272_szabo_strong/: Lean proof, accepted by the bounty site Conjectures.io in September 2026, that the largest family of subsets of the first N integers with pairwise nonempty arithmetic progression intersections has N squared over 2 plus O(N) members, Szabó's linear-error asymptotic and not the exact value, with no refereed publication and the site's kernel check not repeated here.

katz_1999_bounds_arithmetic_projections_applications_kakeya_conjecture/: Improves bounds on difference sets over restricted graphs and deduces that Besicovitch sets in R^n have Minkowski dimension at least 4n/7+3/7.

keevash_2026_non_trivial_bound_3ap_intersecting_families/: Proves a fixed density gap below one half for families whose pairwise intersections contain a nontrivial three-term arithmetic progression, via a bounded-codegree hypergraph theorem, concentration, Plünnecke expansion, and incidence-cycle counting.

kelley_2023_strong_bounds_3_progressions/: Shows any subset of the first N integers of size at least N times 2 to the minus a power of log N has a three-term progression.

kim_pilanci_2026_ai_assisted_discovery_convex_relaxations_via_dual_agents/: Reports the lower bound 0.37912 for the minimum overlap constant from a semidefinite strengthening of the cited convex relaxation, a candidate witness that Problem 36's constant exceeds 0.379005.

kohonen_2017_improved_lower_bound_finite_additive_2/: Constructs generalized Mrose bases showing the maximal range of a finite additive 2-basis of size k is asymptotically at least 85/294 times k squared.

komlos_1975_linear_problems_combinatorial_number_theory/: Proves that for every linear relation and all large n, the largest relation-free subset of any n integers is at least a constant fraction of the largest one in the first n integers, the fraction being one over eight alpha to the sixth for translation-invariant relations.

korsky_2026_arithmetic_progression_free_subset_sum_sets/: Improves lower bounds for the least N whose n-element subsets have progression-free subset-sum sets, for three terms and general k.

kozik_2016_improved_algorithms_colorings_simple_hypergraphs_applications/: Shows simple n-uniform hypergraphs of maximum edge degree at most c n r^(n-1), for an absolute constant c > 0, are r-colorable, and deduces a new van der Waerden number lower bound.

kra_2024_proof_erdos_s_conjecture/: Proves that any set of natural numbers with positive upper density can be shifted to contain the restricted sumset of an infinite subset.

kravitz_2024_rearranging_small_sets_distinct_partial_sums/: Proves Graham's distinct-partial-sums conjecture for subsets of the nonzero residues modulo p of size at most log p over log log p.

lemm_2015_new_counterexamples_sums_differences/: Builds counterexamples from non-uniform probability measures showing that the sums-differences statements SD(0,1,infinity; alpha) and SD(0,1,2,infinity; alpha) fail for some alpha above 1.77898 and, as printed, 1.61226.

leng_2024_improved_bounds_szemeredi_s_theorem/: Shows that sets of integers up to N with no k-term progression have size O(N exp(-(log log N)^{c_k})), with some c_k in (0,1), for every k at least 5.

lev_2017_isoperimetric_stability/: Bounds from below the size of a set with small Cayley-graph edge boundary and bounds from above the independent dimension of popular-difference sets.

lev_yuster_2010_size_dissociated_bases/: Constructs large dissociated subsets of the Boolean cube and compares the sizes of maximal dissociated bases in an arbitrary finite abelian-group set.

lu_2012_monochromatic_4_term_arithmetic_progressions_2/: Gives explicit 2-colorings with far fewer monochromatic 4-term progressions than random, plus improved lower bounds for cyclic groups.

luczak_2000_maximal_density_sum_free_sets/: Shows every sum-free set of natural numbers has counting function below 403 times the square root of n log n infinitely often, nearly optimally.

lunnon_1988_integer_sets_distinct_subset_sums/: Studies minimum-height integer sets with distinct subset sums, including Conway--Guy-type constructions, finite computations, and exact algorithms.

mann_1960_refinement_fundamental_theorem_density_sum_two/: Strengthens the alpha+beta theorem for sumsets and proves more than an Erdős conjecture on simultaneous counting inequalities.

martin_reiner_2004_cyclotomic_simplicial_matroids/: A focused E0774 digest of the arXiv preprint.

martos_et_al_2023_minimun_overlap_problem_finite_groups/: Proves the counting bound |A||B|/|G| on the maximum difference multiplicity for group partitions and builds a squares partition of odd-order fields, giving no bound on Problem 36's constant.

miyazaki_2026_improved_ramsey_bounds_generalized_schur_equations/: Bounds generalized Schur numbers and determines an additive 2^r threshold; neither result transfers to the exact shortest-odd-cycle problem.

mohammadi_2023_attaining_exponent_5_4_sum_product/: Raises the finite-field sum-product exponent to 5/4: for small sets A the larger of the sum set and product set has size at least about |A|^(5/4).

montgomery_vaughan_1979_mean_values_character_sums/: Source record and research digest.

moreira_2019_proof_sumset_conjecture_erdos/: Proves Erdős's sumset conjecture: every set of natural numbers with positive upper density contains B+C for some infinite sets B and C.

moser_1959_minimal_overlap_problem_erdos/: Claims the lower bound (√2/4)(n-1) for the minimum overlap by a second-moment argument whose packing step fails, leaving only its moment identities usable for Problem 36.

moy_2011_growth_counting_function_stanley_sequences/: Proves every Stanley sequence has counting function at least (sqrt 2 - eps) sqrt x, answering a growth question of Erdős and coauthors.

mrose_1979_untere_schranken_reichweiten_extremalbasen_fester_ordnung/: Mrose's 1979 lower bounds for the range of a finite additive basis of fixed order h and k positive elements: a recursive construction (Satz 1) that raises the order by one, giving n_2(k) >= (8/7)(k/2)^2 + O(k), the liminf n(k)/k^2 >= 2/7 that refutes g(n) ~ 2 sqrt(n) for Problem 791, n_3(k) >= (32/27)(k/3)^3 + O(k^2), and Satz 2 for every order h >= 2.

muyesser_2022_random_hall_paige_conjecture/: Proves a random version of the Hall-Paige conjecture and uses it to settle several old problems on transversals and orderings in large finite groups.

odlyzko_1978_curious_sequences_constructed_greedy_algorithm/: Defines the greedy sequences S(k) with no three-term progression starting 0, k, states without proof ternary-digit descriptions of their members when k is 3^m or twice 3^m, and gives a table and a probabilistic heuristic suggesting growth of order n squared over log n for the other, irregular k.

onn_2007_convex_discrete_optimization/: Onn's monograph on maximizing convex functions of linear forms over discrete sets, through edge-directions, Graver bases and n-fold integer programming, with result pages for its main theorems and for the Graver-basis lemma that the E0774 digest uses.

openai_2026_quantitative_superexponential_bounds_van_der_waerden_numbers/: A release manuscript claiming W_r(k) > k^(c k floor(log_2 r)) with c = 10^(-5) for every r >= 2 and every k above one absolute threshold, by a randomly perturbed two-coloring of a cyclic group of prime-power order followed by a digit product; bears on Problems 138 and 169.

openai_2026_quasipolynomial_bounds_arithmetic_progressions/: Claims $r_k(N)\le C_kN\exp(-c_k(\log N)^{\varepsilon_k})$ for every fixed $k\ge3$ by a density increment on triangular polynomial cells, with the Leng--Sah--Sawhney inverse theorem and Schoen--Sisask almost-periodicity as inputs; summed over dyadic blocks, the claimed bound would settle the reciprocal-sum conjecture (Problem 3), and it bears on Problems 139, 140, 142, 169, 201 and 219.

parrilo_2008_asymptotic_minimum_number_monochromatic_3_term/: Bounds the least number of monochromatic 3-term progressions in a 2-coloring of [1,n] between 1675n^2/32768 and 117n^2/2192, each up to a factor 1+o(1).

pham_2024_sharp_bound_erdos_straus_non_averaging/: Determines the largest non-averaging subset of the first n integers as n to the power one quarter plus o(1), solving the Erdos-Straus problem.

pham_2026_graham_s_rearrangement_conjecture/: Proves Graham's rearrangement conjecture for subsets of the nonzero residues mod p of size between a constant depending on alpha and p^(1-alpha), for each alpha in (0,1), which with earlier range results settles it for all large primes p.

polymath_2012_new_proof_density_halesjewett_theorem/: Gives the first elementary and first quantitative proof of the density Hales-Jewett theorem, with a tower-type bound in the three-letter case.

reiher_2024_colouring_versus_density_integers_hales_jewett_cubes/: Builds integer sets where every finite coloring gives a monochromatic k-term progression yet every finite subset Y has a part of size at least mu|Y| with no k-term progression, for any fixed mu < (k-1)/k.

roche_newton_et_al_2026_more_sum_product_type_counterexamples_products_shifts_aa/: Strengthens the real sum-product counterexample to keep products with additive terms and finitely many shifted product sets small, while exposing the growing-degree obstruction to an integer or rational transfer.

rohrbach_1937_ein_beitrag_zur_additiven_zahlentheorie/: Rohrbach's 1937 paper on minimal additive bases: the smallest finite additive 2-basis for {0, ..., n} has fewer than 2 sqrt(n) elements for n > 1 (Satz 3, by the explicit symmetric basis (6)), at least sqrt(2n) elements (the Folgerung to Satz 6) and, for large n, more than sqrt(n/0.4992) elements (inequality (47)); the conjecture n_2(k) = k^2/4 + O(k) that Problem 791 asks about; and bases of order h with fewer than h n^{1/h} elements.

russell_2026_tighter_upper_bound_erdos_minimum_overlap_constant/: Certifies, by exact rational evaluation of explicit step functions, that the minimum overlap constant of Problem 36 is below 0.38085906, without establishing any new lower bound.

ruzsa_1999_erdos_integers/: Ruzsa's 1999 survey of Erdős's work on the integers, in five parts (primes; divisors, sets of multiples and primitive sequences; arithmetical functions; additive problems; miscellany) with the later results that grew out of his questions: it defines essential components and records Erdős's question whether the numbers 2^m 3^n form one, and it states the 1999 bounds on the largest number of integers up to n with all subset sums distinct.

ruzsa_2005_sum_avoiding_subsets/: Ruzsa's 2005 bounds for l(n), the least over n-element sets A of positive integers of the largest subset S with s + s' outside A for all distinct s, s' in S: the Theorem (2/log 3) log n - 1 < l(n) << exp(c sqrt(log n)) for every c > sqrt(8 log 2), the upper half from dilated lattice balls projected to the integers, the lower half from a greedy selection; the upper bound Problem 787's page cites from the paper.

ruzsa_2017_exact_additive_complements/: Improves the lower bound on A(x)B(x) - x for exact additive complements and shows by example that the new bound is nearly optimal.

sanders_2021_erdos_moser_sum_free_set_problem/: Proves every finite set A of N integers contains a subset of size at least log_3^(1+c) N, for an absolute c > 0, whose sums of two distinct elements all lie outside A.

scarf_1985_integral_polyhedra_three_space/: Develops Howe's width-one classification for empty three-dimensional lattice polytopes and its integer-programming consequences.

selfridge_1958_determination_numbers_sums_fixed_order/: Shows that a set of n complex numbers is recovered from its multiset of s-element subset sums unless n is a root of one of a family of explicit equations.

semchankau_2020_maximal_subsets_free_arithmetic_progressions_arbitrary/: Shows that for each k >= 3 and infinitely many dense-in-scale n, every n-element integer set has a k-term-progression-free subset asymptotically at least a quarter the size of the largest one in [1,n].

shkredov_yekhanin_2010_sets_large_additive_energy_symmetric_sets/: Extracts low-dimensional signed-span structure from sets with large additive energy and bounds the dimension of popular-difference sets.

simonovits_1981_intersection_properties_subsets_integers/: Determines to within a factor 1+o(1), for each fixed k >= 2, the largest family of subsets of 1..n whose pairwise intersections are arithmetic progressions of at least k terms.

solymosi_2004_note_question_erdos_graham/: Proves that for every positive density every large enough subset of the N by N grid of that density contains the four vertices of an axis-parallel square, by lifting to three dimensions and the Frankl–Rödl theorem on 3-uniform hypergraphs, with a tower-type bound.

solymosi_2009_bounding_multiplicative_energy_sumset/: Proves |AA||A+A|^2 is at least |A|^4 up to a log factor, giving the sum-product bound max(|A+A|,|AA|) above |A|^{4/3-o(1)}.

steinerberger_2022_remarks_erdos_distinct_subset_sums_problem/: Characterizes separated subset sums by a Fourier integral, derives a near-Gaussian signed-sum mechanism, and bounds dissociated subsets of an initial interval without controlling arbitrary ambient sets in Problem 963.

szabo_1999_intersection_properties_subsets_integers/: Proves that the largest family of subsets of the first n integers whose pairwise intersections are nonempty arithmetic progressions has n squared over 2 plus O(n to the 5/3 times log cubed n) members, confirming the Simonovits–Sós conjecture asymptotically, and gives constructions slightly larger than their conjectured extremal family.

szemeredi_1975_sets_integers_containing_no_elements_arithmetic/: Proves the Erdős–Turán conjecture that a set of integers of positive upper density contains arithmetic progressions of every length.

vu_et_al_2007_mapping_incidences/: Maps any finite part of a characteristic-zero integral domain to finite fields while preserving a prescribed finite set of algebraic incidences, and transfers finite-field sum-product bounds back to characteristic zero.

walker_2022_integer_sets_large_harmonic_sum_which/: Uses digit-restricted Kempner sets to improve lower bounds on the largest harmonic sum of a set avoiding 4-term and 10-term progressions.

wang_2026_proposed_solution_erdos_problem_788/: Claims matching square-root bounds for Choi's function on sum-avoiding subsets, giving the conjectured exponent one half.

white_2022_erdos_minimum_overlap_problem/: Raises the lower bound for the minimum overlap constant to 0.379005, close to the known upper bound 0.380927.

wolf_2010_minimum_number_monochromatic_4_term_progressions/: Improves the lower bound on monochromatic 4-term progressions in any 2-coloring of Z_p and gives a coloring beating the random count.

yang_2026_exact_values_exact_upper_bounds_families_integers_arithmetic_progression_intersections_erdos_problem_272/: Reports exact values through N = 12 and proves Szabó's lower bound is exact among all families with a common element, reducing the proposed general formula to the open kernel question.

ye_et_al_2026_structured_scaling_ai_discovery_across_diverse_scientific_domains/: Studies budget allocation across AI search trajectories, using the minimum overlap problem as a test task whose printed objective is flawed and whose scores certify no bound for Problem 36.

yuksekgonul_2026_learning_discover_test_time/: Machine-learning preprint whose Section 4.1.1 reports a 600-piece step function certifying the upper bound 0.380876 for the constant of Erdős's minimum overlap problem, below AlphaEvolve's 0.380924 and Haugland's 0.380927; the certificate itself is not in the PDF.

zhelezov_palvolgyi_2020_query_complexity_polynomial_freiman_ruzsa_conjecture/: Uses an adaptive coordinate-query form of polynomial Freiman--Ruzsa on prime-valuation vectors to prove near-maximal additive growth for integer sets at the few-products endpoint.

This folder holds sources whose primary subject is Sumsets and Arithmetic Progressions.

Sources with other primary subjects

Explicit links to this subject's problems support these cross-references.

Linked from (163)

Graph