Prize Problem Ledger · PPL
An auditable catalog of mathematical conjectures, existence questions, computational targets and proof challenges with active cash awards, each with a permanent PPL number, primary sources and clearly separated status labels. Cite a target simply as “PPL 017.”
Millennium, Beal & IUT challenges
PPL catalog
Search by PPL number or exact statement, compare reward terms, sort by age, estimated prize value or reference depth, then share a permanent problem ID.
Showing 177 of 177
Cross-currency sorting uses approximate July 2026 reference rates; renewal-pending amounts remain estimates.
Dynamical systems
Determine whether some odd multiplier X≥5 and odd starting value n₀ produce an Xn+1 trajectory that tends to infinity.
Dynamical systems
Prove or disprove that the 9n+1 trajectory starting from 1 tends to infinity.
Dynamical systems
Prove that every odd starting value reaches 1 in the sponsor’s adversarial 3n±1 game under optimal play, or give a counterexample.
Dynamical systems
Starting from any odd positive integer, repeatedly choose 3n+1 or 3n−1 by a fair coin and then remove every factor of 2. Prove that the process reaches 1 almost surely.
Number theory
If Aˣ + Bʸ = Cᶻ for positive integers with x, y and z all greater than 2, then A, B and C must have a common prime factor.
Number theory
For an elliptic curve over the rationals, the order of vanishing of its L-function at s = 1 should equal the rank of its group of rational points.
Recreational mathematics
Construct a 3×3 magic square containing at least seven distinct squared integers that is not a rotation, reflection, or square multiple of the sole known seven-square example; a full square of nine distinct squares also resolves the classical problem.
Recreational mathematics
Construct a 5×5 square of distinct positive integers whose rows, columns and main diagonals have equal sums both before and after every entry is squared, or prove impossibility.
Recreational mathematics
Construct, or prove impossible, a 3×3 semi-magic square using distinct positive cubed integers, with all row and column sums equal.
Recreational mathematics
Construct, or prove impossible, a 4×4 magic square using distinct positive cubed integers.
Recreational mathematics
Construct, or prove impossible, a 5×5 magic square using distinct positive cubed integers.
Recreational mathematics
Construct, or prove impossible, a 6×6 magic square using distinct positive cubed integers.
Recreational mathematics
Construct, or prove impossible, a 5×5 square of distinct positive integers whose rows, columns and main diagonals have both equal sums and equal products.
Recreational mathematics
Construct, or prove impossible, a 6×6 square of distinct positive integers whose rows, columns and main diagonals have both equal sums and equal products.
Cryptography
For the published ECC2-131 instance (random binary-field, 131-bit subgroup), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECC2-163 instance (random binary-field, 163-bit subgroup), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECC2-191 instance (binary-field, 191-bit subgroup), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECC2-238 instance (random binary-field, 239-bit level), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECC2-353 instance (random binary-field, 359-bit level), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECC2K-130 instance (Koblitz binary-field, 131-bit subgroup), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECC2K-163 instance (Koblitz binary-field, 163-bit subgroup), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECC2K-238 instance (Koblitz binary-field, 239-bit level), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECC2K-358 instance (Koblitz binary-field, 359-bit level), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECCp-131 instance (prime-field, 131-bit subgroup), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECCp-163 instance (prime-field, 163-bit subgroup), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECCp-191 instance (prime-field, 191-bit challenge identifier), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECCp-239 instance (prime-field, 239-bit level), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Cryptography
For the published ECCp-359 instance (prime-field, 359-bit level), compute the private scalar ℓ satisfying ℓP=Q and document the complete method.
Number theory
Starting from any positive integer, repeatedly halve it when even and replace it by 3n + 1 when odd. Must the sequence always reach 1?
Computational number theory
Through GIMPS, discover a new Mersenne prime 2ᵖ − 1 below 100 million decimal digits and satisfy the program’s verification rules.
Cryptography
Recover the unknown 72-bit key and plaintext for distributed.net’s published RC5-32/12/9 ciphertext, ordinarily by contributing verified key-space work to the live distributed search.
Coding theory
Determine whether an extremal Type II binary self-dual code with parameters [72,36,16] exists.
Number theory
If A⊆ {1,…,N} with | A|=n is such that the subset sums ∑_(a∈ S)a are distinct for all S⊆ A then N ≫ 2^(n).
Geometry
Given n points in ℝ^2, no five of which are on a line, the number of lines containing four points is o(n^2).
Graph theory
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)}→ ∈fty.
Geometry
Given n points in ℝ^2 the number of distinct unit circles containing at least three points is o(n^2).
Number theory
A unitary divisor of n is d∣ n such that (d,n/d)=1. A number n≥ 1 is a unitary perfect number if it is the sum of its unitary divisors (aside from n itself). Are there only finite many unitary perfect numbers?
Additive combinatorics
Determine the sharp lower-density behavior possible for infinite Sidon sets, including whether the known density barriers can be attained or improved.
Combinatorics
Let A⊆ℝ be an infinite set. Must there be a set E⊂ ℝ of positive measure which does not contain any set of the shape aA+b for some a,b∈ℝ and a≠ 0?
Number theory
Let f(n) be maximal such that if A⊆ℕ has | A|=n then ∏_(a≠ b∈ A)(a+b) has at least f(n) distinct prime factors. Is it true that f(n)/log n→∈fty?
Distances
Let A⊂ ℝ^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 → ∈fty as n→ ∈fty?
Additive combinatorics
Let the van der Waerden number W(k) be such that whenever N≥ W(k) and {1,…,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)→ ∈fty.
Additive combinatorics
Let r_k(N) be the largest possible size of a subset of {1,…,N} that does not contain any non-trivial k-term arithmetic progression. Prove an asymptotic formula for r_k(N).
Primitive sets
Let A⊂ (1,∈fty) be a countably infinite set such that for all x≠ y∈ A and integers k≥ 1 we have | kx -y| ≥ 1. Does this imply that A is sparse? In particular, does this imply that ∑_(x∈ A)(1/xlog x)<∈fty or ∑_{\substack{x <n\\ x∈ A}}(1/x)=o(log n)?
Graph theory
If H is bipartite and is r-degenerate, that is, every induced subgraph of H has minimum degree ≤ r, then ex(n;H) ≪ n^(2-1/r).
Combinatorics
Let α∈[0,1/2) and n,t≥ 1. Let F^((t))(n,α) be the largest m such that we can 2-colour the edges of the complete t-uniform hypergraph on n vertices such that if X⊆ [n] with | X| ≥ m then there are at least α C(| X|, t) many t-subsets of X of each colour. For fixed n,t as we change α from 0 to 1/2 does F^((t))(n,α) increase continuously or are there jumps? Only one jump?
Graph theory
Let R(3;k) be the minimal n such that if the edges of K_n are coloured with k colours then there must exist a monochromatic triangle. Determine \lim_(k→ ∈fty)R(3;k)^(1/k).
Combinatorics
Let f(n,k) be minimal such that every family F of n-uniform sets with | F| ≥ f(n,k) contains a k-sunflower. Is it true that f(n,k) < c_k^n for some constant c_k>0?
Additive combinatorics
Let f(N) be the maximum size of A⊆ {1,…,N} such that the sums a+b+c with a,b,c∈ A are all distinct (aside from the trivial coincidences). Is it true that f(N)\sim N^(1/3)?
Number theory
If A⊆ ℕ is such that A+A contains all but finitely many integers then limsup 1_A∗ 1_A(n)=∈fty.
Number theory
If A⊆ ℕ has ∑_(n∈ A)(1/n)=∈fty then must A contain arbitrarily long arithmetic progressions?
Number theory
Let h(N) be the maximum size of a Sidon set in {1,…,N}. Is it true that, for every ε>0, h(N) = N^(1/2)+O_ε(N^ε)?
Number theory
Is there an infinite Sidon set A⊂ ℕ such that | A∩ {1…,N}| ≫_ε N^(1/2-ε) for all ε>0?
Number theory
For what functions g(N)→ ∈fty is it true that | A∩ {1,…,N}| ≫ \frac{N^(1/2)}{g(N)} implies limsup 1_A∗ 1_A(n)=∈fty?
Number theory
Let A⊂ℕ be an infinite set such that the triple sums a+b+c are all distinct for a,b,c∈ A (aside from the trivial coincidences). Is it true that liminf \frac{| A∩ {1,…,N}|}{N^(1/3)}=0?
Number theory
Call n weird if \sigma(n)≥ 2n and n is not pseudoperfect, that is, it is not the sum of any set of its divisors. Are there any odd weird numbers? Are there infinitely many primitive weird numbers, i.e. those such that no proper divisor of n is weird?
Number theory
Schoenberg proved that for every c∈ [0,1] the density of { n∈ ℕ : φ(n)<cn} exists. Let this density be denoted by f(c). Is it true that there are no x such that f'(x) exists and is positive?
Graph theory
What is 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.
Number theory
Let A be a finite set of integers. Is it true that for every ε>0 max( | A+A|,| AA|)≫_ε | A|^(2-ε)?
Graph theory
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. Is there some constant c>0 such that R_3(n) ≥ 2^{2^(cn)}?
Geometry
Let f_k(n) be minimal such that if n points in ℝ^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≥ 4?
Set theory
Determine which countable ordinals β have the property that, if α=ω^(^β), then in any red/blue colouring of the edges of K_α there is either a red K_α or a blue K_3.
Set theory
Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number >\aleph_0.
Graph theory
Is there an infinite graph G which contains no K_4 and is not the union of countably many triangle-free graphs?
Graph theory
For which limit ordinals α is it true that if G is a graph with vertex set α then G must have either an infinite path or independent set on a set of vertices with order type α?
Geometry
Given n distinct points A⊂ℝ^2 must there be a point x∈ A such that \#{ d(x,y) : y ∈ A} ≫ n^(1-o(1))? Or even ≫ n/√(log n)?
Graph theory
The cochromatic number of G, denoted by ζ(G), is the minimum number of colours needed to colour the vertices of G such that each colour class induces either a complete graph or empty graph. Let χ(G) denote the chromatic number. If G is a random graph with n vertices and each edge included independently with probability 1/2 then is it true that almost surely χ(G) - ζ(G) → ∈fty as n→ ∈fty?
Geometry
Find all n such that there is at least one triangle which can be cut into n congruent triangles.
Number theory
Is there A⊆ ℕ such that \lim_(n→ ∈fty)(1_A∗ 1_A(n)/log n) exists and is ≠ 0?
Geometry
Are there, for all large n, some points x_1,…,x_n,y_1,…,y_n∈ ℝ^2 such that the number of distinct distances d(x_i,y_j) is o((n/√(log n)))?
Analysis
Given a_(i)^n∈ [-1,1] for all 1≤ i≤ n<∈fty 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≤ i'≤ n with i≠ i'. We similarly define L^nf(x) = ∑_(1≤ i≤ 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≤ i≤ n (that is, the sequence of Lagrange interpolation polynomials). Is there such a sequence of a_i^n such that for every continuous f:[-1,1]→ ℝ there exists some x∈ [-1,1] where \limsup_(n→ ∈fty) ∑_(1≤ i≤ n)| p_(i)^n(x)|=∈fty and yet L^nf(x) → f(x)? Is there such a sequence such that \limsup_(n→ ∈fty) ∑_(1≤ i≤ n)| p_(i)^n(x)|=∈fty for every x∈ [-1,1] and yet for every continuous f:[-1,1]→ ℝ there exists x∈ [-1,1] with L^nf(x) → f(x)?
Number theory
Let Y(x) be the maximal y such that there exists a choice of congruence classes a_p for all primes p≤ x such that every integer in [1,y] is congruent to at least one of the a_p\pmod{p}. Give good estimates for Y(x). In particular, can one prove that Y(x)=o(x^2) or even Y(x)≪ x^(1+o(1))?
Number theory
Let g(n) be minimal such that for any A⊆ [2,∈fty)∩ ℕ with | A| =n and any set I of max(A) consecutive integers there exists some B⊆ I with | B|=g(n) such that ∏_(a∈ A) a ∣ ∏_(b∈ B)b. Is it true that g(n) ≤ (2+o(1))n? Or perhaps even g(n)≤ 2n?
Number theory
Let f(n) be minimal such that in (n,n+f(n)) there exist distinct integers a_1,…,a_n such that k∣ a_k for all 1≤ k≤ n. Obtain an asymptotic formula for f(n).
Number theory
Let f(n,m) be minimal such that in (m,m+f(n,m)) there exist distinct integers a_1,…,a_n such that k∣ a_k for all 1≤ k≤ n. Prove that \max_m f(n,m) ≤ n^(1+o(1)) and that \max_m (f(n,m)-f(n,n))→ ∈fty.
Graph theory
Determine, for any k>r>2, the value of (ex_r(n,K_k^r)/C(n, r)), where 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 C(k, r) possible r-edges.
Graph theory
Is it true that, for every bipartite graph G, there exists some α∈ [1,2) and c>0 such that ex(n;G)\sim cn^α? Must α be rational?
Graph theory
Let f(n)→ ∈fty (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on n vertices can be made bipartite by deleting at most f(n) edges?
Graph theory
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→ ∈fty)R(k)^(1/k).
Graph theory
Give a constructive proof that R(k)>C^k for some constant C>1.
Graph theory
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 ≥ ((1/2)+o(1))n2^(n-1) many edges contains a C_4?
Geometry
Does every set of n distinct points in ℝ^2 determine ≫ n/√(log n) many distinct distances?
Geometry
Let A⊆ℝ^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?
Computational number theory
Be the first to identify and reproducibly certify a prime number with at least 100,000,000 decimal digits.
Computational number theory
Be the first to identify and reproducibly certify a prime number with at least 1,000,000,000 decimal digits.
Numerical analysis
For a polynomial p of degree at most n at the specified Gauss or Radau nodes, prove the reverse-Markov bounds in Hager’s statement: p(−1)=0 and bounded nodal derivatives should force bounded nodal values.
Algebraic geometry
On a smooth projective complex algebraic variety, every rational Hodge class should be a rational linear combination of classes of algebraic cycles.
Number theory
Every integer n>4 is the sum of an odd prime, a positive Fibonacci number and a Catalan number.
Theoretical computer science
Prove or disprove Stephen Wolfram’s conjecture that the S combinator alone—without K or other primitive combinators—is computation-universal.
Arithmetic geometry
Publish the first qualifying paper that demonstrates an essential and inherent flaw in Shinichi Mochizuki’s inter-universal Teichmüller theory.
Quantum information
Give an infinite sequence of dimensions with explicit symmetric informationally complete generalized quantum measurements, or prove that only finitely many such dimensions exist.
Quantum information
Find four mutually unbiased bases in dimension 6, or prove that there are no seven mutually unbiased bases in that dimension.
Quantum information
Determine whether bound-entangled states with negative partial transpose exist.
Quantum information
Show that the symmetric two-ququart Werner state whose partial transpose is proportional to a unitary operator is two-copy non-distillable.
Combinatorics on words
Settle any one of five questions about the Oldenburger–Kolakoski sequence: find a formula for its nth term; prove recurrence of every occurring finite word; prove reversal closure; prove closure under swapping 1 and 2; or prove that the limiting frequency of 1 exists and equals one half.
Geometry
Find and prove optimal parametric equations for a simple closed curve of length 4π on the unit sphere that minimizes mean spherical distance from the sphere to the curve; ideally solve the version for every length L > 2π.
Combinatorics on words
For the unique nontrivial binary sequence s with s(1)=1 and r(r(s))=s, prove or disprove that every finite segment of its run-length sequence r(s) also occurs in s.
Number theory
In Kimberling’s prime-separator array, prove or disprove that the successive differences in the first row are bounded.
Combinatorics
Prove or refute that the self-generated sequence a(k) in Kimberling’s two-sequence algorithm runs through all positive integers.
Combinatorics
Prove or refute that the companion difference sequence d(k) in Kimberling’s two-sequence algorithm runs through all integers.
Combinatorics
Prove or refute that whenever d(k)>0, at least one of d(k+1), d(k+2), or d(k+3) is positive.
Combinatorics
Prove or refute that whenever d(k)<0, at least one of d(k+1), d(k+2), or d(k+3) is negative.
Number theory
Prove or disprove that every row of Kimberling’s triangular-number interspersion array contains infinitely many primes.
Enumerative combinatorics
Enumerate the arrangements of 1 through n(n+1)/2 in a triangular array such that every entry in a row lies between the two adjacent entries immediately below it.
Number theory
Prove or disprove that every positive integer occurs in the sequence beginning 1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, ….
Number theory
Characterize the real numbers r for which the Beatty sequence floor(nr) contains a homogeneous linearly recurrent subsequence.
Combinatorics
In Kimberling’s iterative counting process, prove or disprove that every positive integer is eventually written; the general form allows any finite positive initial count with distinct labels.
Graph theory
Resolve the Krenn-Gu conjecture on monochromatic inherited vertex colorings of edge-colored weighted graphs—either by proof or counterexample.
Number theory
Find a finite-case arithmetic formula f that universally approximates the sponsor’s t_space_(n₁,n₂,n₃)(x) within n₃²/2.
Number theory
For primes n₁<n₂<n₃ and n>1, prove that positive h+k=n exist such that neither n₁h−1 nor n₁k+1 is divisible by n₂ or n₃.
Number theory
Prove the sponsor’s stated finite-index f/g representation for positive x avoiding all specified nᵢ when x+1 is divisible by n₁.
Cryptography
Find a collision in the specified 220-round MiMCSponge / MiMC-Feistel construction over the BLS12-381 scalar field.
Cryptography
Find a collision in the specified 220-round MiMCSponge / MiMC-Feistel construction over the BN254 scalar field.
Algorithms
Given a hidden directed unweighted graph where cut(S) returns the number of edges leaving S, either give an O(|V|^1.999)-query algorithm for s–t reachability or rule out O(|V|^1.001) queries; a smaller sub-bounty asks for any improvement below O(|V|²/log n).
Theoretical computer science
In a Turing-machine or RAM model, determine whether a decision problem P can have a 10n-time algorithm, a particular 100n²-time algorithm A, yet every 10n-time algorithm for P has a description strictly larger than A.
Algorithms
Prove or disprove the Online Matrix–Vector Multiplication conjecture: no truly subcubic algorithm solves the standard online Boolean matrix–vector product problem.
Algorithms
Prove or disprove the v-hinted Matrix–Vector conjecture, Conjecture 5.2 of van den Brand, Nanongkai and Saranurak.
Partial differential equations
Resolve global existence and smoothness for the three-dimensional incompressible Navier–Stokes equations under the official conditions, or exhibit finite-time breakdown.
Formal languages
Is there a universal constant k such that every Boolean-grammar language has a Boolean grammar using at most k nonterminal symbols?
Formal languages
Is there a fixed k₀ such that Boolean LL(k) grammars generate the same language family as Boolean LL(k₀) grammars for every k≥k₀?
Formal languages
Is the family of languages generated by conjunctive grammars closed under complementation?
Formal languages
Does every Boolean grammar have an equivalent Boolean grammar in Greibach normal form?
Formal languages
Does any language exist that is inherently ambiguous with respect to Boolean grammars?
Formal languages
Are there languages recognized in O(n²) time by deterministic linear-bounded automata that cannot be specified by Boolean grammars?
Formal languages
Are the languages generated by Boolean grammars contained in deterministic space O(n^(1−ε)) for some ε>0?
Theoretical computer science
If a solution can be checked efficiently, can it also be found efficiently? Equivalently: is P equal to NP?
Cryptography
Find a degree-7 polynomial over the stated quadratic extension field whose root is formed from the first two Poseidon1 RF=6 outputs, and set a new record for the number of partial rounds broken beyond the already verified records.
Cryptography
Improve the published best reduced-round attack against Poseidon-256 and break a specified security property under the program’s formal rules.
Cryptography
Improve the published best reduced-round attack against Poseidon-31 and break a specified security property under the program’s formal rules.
Cryptography
Improve the published best reduced-round attack against Poseidon-64 and break a specified security property under the program’s formal rules.
Cryptography
For the published 15-element Poseidon1/KoalaBear input instance H(0xc09de4,·), find two distinct inputs whose first q output elements collide, for any still-open milestone q=4,5,6,7.
Coding theory
For the formal prize parameters, determine the largest normalized distance δ* for which the relevant Reed–Solomon list size remains at most the target fraction of the field.
Coding theory
For constant-rate Reed–Solomon codes over the specified smooth domains and rates, determine the largest normalized distance δ* for which the maximum-correlated-agreement error meets the target security level.
Numerical analysis
Prove and publish mesh-size-independent Scott–Vogelius inf-sup stability in three dimensions on the Freudenthal mesh for polynomial degree k≥4, or publish an analytical refutation.
Partial differential equations
Prove the existence of a nonconstant time-periodic two-dimensional Navier–Stokes solution for flow around a cylinder in the indicated Reynolds-number regime, roughly 50–1000, or prove that none exists.
Numerical analysis
Publish a proof that the Scott–Vogelius–Nitsche method converges on curved boundaries, including the required computational study of the penalty parameter—or explain rigorously why the expected error rate fails.
Number theory
Every non-trivial zero of the Riemann zeta function has real part 1/2.
Cellular automata
Prove or disprove that 0 and 1 occur with asymptotically equal frequency in the center column of Rule 30.
Cellular automata
Prove or disprove that the center column of the Rule 30 cellular automaton is non-periodic.
Cellular automata
Prove or disprove that computing the nth center-column cell of Rule 30 necessarily requires at least order-n computational effort.
Formal languages
Improve Robson’s O(n²⁄⁵(log n)³⁄⁵) upper bound on the number of DFA states needed in the worst case to separate two distinct length-n words.
Formal languages
Under finite-state transduction equivalence, is the Thue–Morse infinite word prime?
Formal languages
Do the limiting frequencies of 1 and 2 exist in the Oldenburger–Kolakoski word, and are both equal to one half?
Formal languages
Is it decidable whether a given base-k DFA accepts the representation of at least one prime number?
Formal languages
Is it decidable whether a DFA over pairs of base-k digits accepts some pair of integers (x, y) with x dividing y?
Formal languages
Given an NFA, decide whether it accepts every word of some length. The problem is PSPACE-hard; is it in PSPACE?
Formal languages
Determine the computational complexity of deciding, from a finite language L, whether L* is infinite.
Formal languages
Determine the complexity of deciding whether every finite word occurs as a contiguous factor of a word in L*, for a finite list L.
Formal languages
Close the gap between quadratic lower examples and the doubly exponential upper bound for the shortest word missing from the factors of L*.
Formal languages
Significantly improve either the known upper or lower bound for the maximum length of a Pierce expansion as a function of its numerator.
Formal languages
Find matching upper and lower bounds for the number of productions needed by a Chomsky-normal-form context-free grammar to separate equal-length words.
Formal languages
Find strong asymptotic bounds on the smallest nondeterministic finite automaton separating any two distinct words of length n.
Formal languages
Find good bounds on the worst-case ratio between deterministic and nondeterministic state complexity for separating two words.
Formal languages
Is the change in deterministic separating complexity between a pair of words and their reversals unbounded?
Formal languages
Given context-free L₁ ⊆ L₂ with infinite difference, must there be a context-free L₃ strictly interpolating them with both remaining differences infinite?
Formal languages
Determine whether the language of primitive—non-power—words over the binary alphabet is context-free.
Formal languages
Does an infinite sequence on three real values exist for which every Hankel determinant of every order is nonzero?
Formal languages
Does the fixed point generated by 1→12, 2→23, 3→14, 4→32 have all of its Hankel determinants nonzero?
Cryptography
Construct a 3-linear map with unique encodings, no noise and a plausibly hard discrete-logarithm problem, under the exact challenge description.
Cryptography
Decide whether statistical zero knowledge equals perfect zero knowledge, equivalently by transforming every SZK proof into a PZK proof under the challenge’s formulation.
Cryptography
Construct indistinguishability obfuscation from the plain Learning With Errors assumption, without the stronger circular, evasive or succinct-LWE-style assumptions used in later work.
Cryptography
For computations in DTISP(t,s), construct interactive proofs with prover time polynomial in t and verifier time polynomial in s for the full parameter range stated by the proposer.
Cryptography
Construct a cryptographic one-way permutation from a worst-case lattice assumption alone, or prove the requested implication impossible under the stated model.
Number theory
Every integer n>5 is the sum of an odd prime, a Pell number and twice a Pell number; the two Pell numbers may both be required positive.
Number theory
Every integer n>4 is the sum of an odd prime and two positive Fibonacci numbers, with one of the Fibonacci numbers odd.
Number theory
For every positive integer m, find consecutive primes pₖ,…,pₙ within Sun’s stated bounds whose alternating sum pₙ−pₙ₋₁+⋯+(−1)ⁿ⁻ᵏpₖ equals m.
Group theory
If a₁G₁,…,aₖGₖ are pairwise disjoint left cosets of finite-index subgroups of a group G, prove that gcd([G:Gᵢ],[G:Gⱼ])≥k for some i<j.
Number theory
Prove both that every natural number except 216 is a prime-or-zero plus a triangular number, and that every odd integer greater than 3 is a prime plus x(x+1) for some positive integer x—or give an explicit counterexample to either part.
Number theory
For each positive rational r and each sign d∈{−1,+1}, prove that r is a finite sum of reciprocals 1/(qⱼ+d) using distinct primes qⱼ.
Number theory
For every integer n>1, there is an integer k with 0≤k<n such that both n+k and n+k² are prime.
Number theory
Every nonnegative integer n can be written as x²+y²+z²+w² with nonnegative integers x,y,z,w such that x+3y+5z is itself a square.
Number theory
Every nonnegative integer n can be written as x²+y²+z²+w² with nonnegative integers x,y,z,w such that both x and x+24y are perfect squares.
Number theory
For every integer n>1, prove that there is an integer k with 1≤k<n for which 2ᵏ+n−k is prime.
Probability
For biased product measure Pδ on {0,1}ᴺ, prove Talagrand’s dimension-free q-covering assertion for every high-measure family D—or meet the prize PDF’s stated weaker bound using a parameter δ′ depending only on δ.
Probability
For two independent uniform N-point samples in the unit square and exponents α₁,α₂ with 1/α₁+1/α₂=1/2, prove Talagrand’s universal-probability matching bounds; either special target (∞,2) or (4,4) earns the full prize.
Mathematical physics
For every compact simple gauge group, construct a non-trivial quantum Yang–Mills theory on four-dimensional space that satisfies the official axioms and has a positive mass gap.
Method, not mythology
The problem must have an objective mathematical resolution: proof, disproof, construction, certified computation or a defined verification result.
The amount, sponsor and claim conditions must be traceable. General research grants, medals and expired competitions are excluded.
“Verified open,” “source-stated,” “renewal check” and “reconfirm sponsor” are deliberately different. Personal and discretionary awards are never presented as escrowed guarantees.
Private bounties appear, change and disappear without a central registry. This edition favors completeness where authoritative data exists—especially the Millennium and Erdős collections—and transparent uncertainty everywhere else.
Source hierarchy
Official problem pages, legal terms and sponsor-maintained records.
Erdős Problems and its machine-readable status file, with direct dossiers.
Original papers and bibliographies used to qualify dates and formulations.