Each problem states how progress is verified and what counts as a contribution. Besides the problems curated here, the catalogue includes open conjectures from Formal Conjectures (with Lean statements), optimization constants and the AlphaEvolve problems. Know one that belongs here? Propose a problem.
106 shown· page 2 of 3
Let D=\z∈ℂ:lvert zrvert<1\ and let F be the class of holomorphic functions f:D→ℂ normalized by f'(0)=1. <a href="#BS2023-def-F">[BS2023-def-F]</a> For finF, let L_f denote the radius of the largest disk contained in f(D).
C_13b = a is the infimal area of a convex planar set Ω that can cover a congruent copy of every convex planar set of diameter 1.
Let f(x)=Σ_i=0^n a_i x^i = a_nΠ_i=1^n (x-α_i) be a polynomial with complex coefficients. The Mahler measure of f is M(f) := |a_n|Π_i=1^n max1,|α_i|.
Define the infimal exponent μ_ζ by μ_ζ := infBiglθ≥ 0: lvertζ(1/2+it)rvert≪_ε(1+lvert trvert)^θ+ε for all ε>0Bigr. We define C_62a := μ_ζ, the Lindelof (pointwise growth) exponent for ζ(1/2+it).
For integers q≥ 2 and a with gcd(a,q)=1, let P(a,q) denote the least prime in the arithmetic progression a bmod q. <a href="#Xyl2011-def-Paq">[Xyl2011-def-Paq]</a> Linnik's theorem asserts that there exist constants C,L>0 such that P(a,q) ≤ C q^L (gcd(a,q)=1), uniformly for all q≥ 2.
Let K⊂ℝ^n be a centrally symmetric convex body (compact, convex, with non-empty interior) satisfying K=-K. Its polar body is K^∘ := y∈ℝ^n: ⟨ x,y⟩ ≤ 1 for all x∈ K. The volume product of K is vp(K) := Vol_n(K) Vol_n(K^∘).
For a number field K, let Δ_K denote the absolute value of its discriminant and let [K:ℚ] denote its degree. The root discriminant of K is rd(K) := Δ_K^1/[K:ℚ].
C_18 is the least constant such that, whenever A is a subset of 𝔽_2^n with lvert A+Arvert ≤ Klvert Arvert, then A can be covered by K^C_18+o(1) cosets of a subspace of cardinality at most lvert Arvert, where the limit o(1) is with respect to the limit K → ∞.
Let f:0,1^n→0,1 be a Boolean function. Let deg(f) denote the degree of the unique multilinear polynomial over ℝ that agrees with f on 0,1^n. A variable x_i is relevant if f depends on it (equivalently: x_i appears in some monomial with nonzero coefficient in the multilinear representation of f).
C_27b is the highest possible chromatic number for any biplanar graph.
In the symmetric metric traveling salesman problem, one is given a complete graph K_n=(V,E) with a nonnegative symmetric cost function c:E→ ℝ_≥ 0 satisfying the triangle inequality. For S⊆ V, let δ(S) denote the set of edges with exactly one endpoint in S, and write δ(v):=δ(\v\).
C_13a is the infimal area of a convex domain Ω that can contain a rigid motion (translation + rotation; no reflections) of every planar arc (curve, or "worm") of length 1.
The moving sofa constant C_41a=A is the maximum area of a connected, rigid planar shape that can maneuver through an L-shaped corridor of unit width. The corridor is formed by two semi-infinite strips of width 1 meeting at a right angle.
For integers m,n≥ 1, let B_ℝ,m(n) be the smallest constant such that every m-linear form T:(ℓ_∞^n)^m → ℝ satisfies the (multilinear) Bohnenblust–Hille inequality (Σ_j_1,…,j_m=1^n bigl|T(e_j_1,…,e_j_m)bigr|^2m/m+1)^m+1/2m ≤ B_ℝ,m(n) ‖T‖, where ‖T‖:=sup_‖x^(1)‖_∞,…,‖x^(m)‖_∞ ≤…
Let X be an integrable real random variable. We say that X is 1-sub-Gaussian in the tail sense if E[X]=0 quadand ℙ(lvert Xrvert>t)≤ 2e^-t^2/2quadfor all t≥ 0.
Let χ be a primitive Dirichlet character modulo q, and define S(χ) := max_N≤ q lvertΣ_1≤ n≤ Nχ(n)rvert. The Polya-Vinogradov inequality states that S(χ) ≤ c √(q) log q for some absolute constant c. <a href="#BK2020-def-PV">[BK2020-def-PV]</a> For squarefree moduli, define C_72^even (resp.
Given a real matrix A, let its condition number be κ(A):=σ_max(A)/σ_min(A), where σ_min(A) and σ_max(A) denote the smallest and largest singular values of A, respectively (with κ(A)=∞ if σ_min(A)=0).
C_46 is the infimal exponent p such that one has the global bound ‖widehatf dσ‖_L^p(ℝ^3) lesssim_p ‖f‖_L^∞(S^2) qquadfor all f∈ L^∞(S^2).
For subsets K,L⊂ℝ^n, their Minkowski sum is K+L := x+y: x∈ K, y∈ L. In general, one cannot expect a reverse Brunn-Minkowski inequality for arbitrary compact sets, even with a fixed multiplicative constant.
C_45 is the asymptotic density (if it exists) of the set of odd integers that can be expressed as the sum of a prime number and a power of two.
An algebraic integer α of degree d, with conjugates α_1,…,α_d, is totally positive if all of its conjugates are real and strictly positive. Its absolute trace (or trace-to-degree ratio) is overlinetr(α) := tr(α)/deg(α) = 1/dΣ_i=1^d α_i . Let A denote the set of totally positive algebraic integers.
Let Γ⊂ SL_2(ℤ) be a congruence subgroup. Denote by 0=λ_0<λ_1(Γ)≤ λ_2(Γ)≤ ⋯ the eigenvalues of the (non-Euclidean) Laplacian acting on L^2(ΓbackslashH).
Let f:ℂ→ℂ be a polynomial of degree n≥ 2 whose zeroes all lie in the closed unit disk D(0,1)=\z:lvert zrvert≤ 1\. Sendov's conjecture states that if λ_0 is one of these zeroes, then f' has at least one zero in D(λ_0,1). every zero λ_0 of f has a critical point in D(λ_0,1).
Let C_7 denote the cycle graph on 7 vertices. We define C_9 to be the Shannon capacity of mathcal C_7: C_9 := Θ(mathcal C_7), where for a graph G, the Shannon capacity Θ(G) is defined by Θ(G) := sup_n ≥ 1 α(G^boxtimes n)^1/n.
C_5b is the largest constant such that every (4,5)-set of size n (i.e., a set of reals such that every four-element subset determines at least five distinct differences) contains a Sidon set of cardinality C_5bn.
For a finite nonempty subset A of an abelian group, write σ(A) := |A+A|/|A|, δ(A) := |A-A|/|A| for the doubling and difference constants. Ruzsa [Ru96] proved δ ≤ σ^2, and the Plünnecke–Ruzsa inequalities give the converse σ ≤ δ^2 [Bl26].
For a bounded set X⊂ ℝ^n, its diameter is diam(X) := sup‖x-y‖_2: x,y∈ X. Let b(X) be the smallest integer m such that X can be written as a union X = X_1 ∪ ⋯ ∪ X_m with diam(X_i) < diam(X) for all i=1,…,m.
C_14 is the smallest n, such that the value of the busy beaver number BB(n) is undecidable in ZFC (or equivalently ZF). Explicitly, it is the smallest n such that there is a Turing machine with n states for which it cannot be proven in ZFC (assuming ZFC is consistent) whether it halts or not.
C_10c is the least constant K for which one has disc(A) ≤ K√(n) qquadfor all n and all A∈[-1,1]^n× n. Here the discrepancy disc(A) is defined as disc(A) := min_x∈± 1^n ‖Ax‖_∞.
C_36=Δ_4 is the (optimal) sphere packing density in ℝ^4, i.e. the largest fraction of ℝ^4 that can be covered by congruent balls with disjoint interiors.
Let ℤ^2 denote the square lattice graph with vertex set ℤ^2 and edges between nearest neighbors (Euclidean distance 1). A self-avoiding walk (SAW) on a graph G=(V,E) is a walk that visits no vertex more than once.
Let Av_n(1324) be the set of permutations of \1,2,…,n\ that avoid the permutation pattern 1324, and let S_n(1324) := |Av_n(1324)|. <a href="#CJS12-def-Sn">[CJS12-def-Sn]</a> The Stanley–Wilf limit (growth constant) for the pattern 1324 is C_30 := lim_n→∞ bigl(S_n(1324)bigr)^1/n.
For a finite set A ⊂ ℝ write A+A = \ a+b : a,b ∈ A \, AA = \ ab : a,b ∈ A \ for the sumset and product set. The (real) sum-product exponent is C_84b := liminf_n → ∞ min_substackA ⊂ ℝ \ lvert Arvert = n log max(lvert A+Arvert, lvert AArvert)/log n.
C_12 = β_2 is the constant such that the length L_n of the shortest tour through n independent uniform random points satisfies L_n/√(n)→ β_2 almost surely.
Let X_1,X_2,… be i.i.d. real random variables with E X_1 = 0, Var(X_1)=1, and finite third absolute moment β_3 := E|X_1|^3 < ∞. Let S_n := X_1+⋯+X_n/sqrt n, F_n(x):=ℙ(S_n≤ x), and let Φ denote the standard normal distribution function.
Let G be a simple graph. The acyclic chromatic index χ_a'(G) of G is defined to be the least number of colors needed to color the edges of G so that no two edges coincident on the same vertex are homochromatic and there is no cycle whose edges are colored with only two colors.
The complex Grothendieck constant (often denoted K_G^ℂ) is the smallest number C_10b such that, for every m,n≥ 1 and every complex matrix A=(a_ij)∈ℂ^m× n, max_substacku_1,…,u_m∈ S^∞\ v_1,…,v_n∈ S^∞ |Σ_i=1^mΣ_j=1^n a_ij⟨ u_i, v_j⟩| ≤ C_10b\ max_substack|s_1|=⋯=|s_m|=1\ |t_1|=⋯=|t_n|=1…
Let m,n be positive integers and let V be a set of n Boolean variables. By a random formula of density r = m/n, we mean a collection of m clauses selected u.a.r. with replacement from the set of 8C(n, 3) clauses on three distinct variables from V.
Let Q_n = -1,1^n be the Hamming cube (two vertices are adjacent if they differ in exactly one coordinate). For a set A ⊂ Q_n define the function h_A:Q_n→ 0,1,...,n by - h_A(x)=0 if x∉ A; - if x∈ A, then h_A(x) is the number of neighbors of x that lie in the complement A^c.
C_2 is the Crouzeix constant (sometimes denoted Q). It is the smallest constant C such that for every n ≥ 1, every complex matrix A ∈ ℂ^n × n, and every complex polynomial p one has ‖p(A)‖ ≤ C max_z ∈ W(A) |p(z)|, where ‖·‖ is the operator norm induced by the Euclidean norm (i.e.
Let f be a Boolean function on n bits, i.e. f:0,1^n → 0,1 with n≥ 2. For x∈ 0,1^n and 1≤ i≤ n, let x^(i) be x with the i-th bit flipped. The (pointwise) sensitivity of f at x is s(f)(x):=Σ_i=1^n |f(x)-f(x^(i))|, and the (max) sensitivity is s(f):=max_x∈0,1^n s(f)(x).
C_3a is the largest constant such that there exist arbitrarily large sets A,B of integers such that |A+B| ≪ |A| and |A-B| ≫ |A+B|^C_3a.
For a real number γ, its irrationality exponent μ(γ) is defined by μ(γ) := infBiglc∈ℝ: Bigllvertγ-a/bBigrrvert≤ lvert brvert^-c has only finitely many solutions (a,b)∈ℤ^2Bigr. <a href="#Zud2004-def-mu">[Zud2004-def-mu]</a> We define C_7b := μbigl(Γ(1/4)bigr).
We define C_7a to be the irrationality measure of π: C_7a := sup_μ∈ℝ μ such that lvert π - p/q rvert < q^-μ for infinitely many rationals p/q. Equivalently, C_7a is the infimum of all ν such that for every ε>0 there exists q_0(ε) with |π-p/q| > 1/q^ν+ε for all integers p and all integers q ≥ q_0(ε).
Let μ be a Borel probability measure on ℝ^n with finite second moments. Its covariance matrix is Cov(μ) :=\ ∫_ℝ^n (x-m)(x-m)^mathsf T dμ(x), m:=∫_ℝ^n x dμ(x). ### Convex bodies If K⊂ℝ^n is a convex body, let λ_K be the uniform probability measure on K and abbreviate Cov(K):=Cov(λ_K).
C_20c is the KLS constant (Kannan–Lovász–Simonovits constant) for log-concave measures. It is defined as C_20c := sup_n≥ 1 ψ_n, where ψ_n is the worst-case inverse Cheeger (isoperimetric) constant among isotropic log-concave probability measures on ℝ^n.
C_11a is the smallest constant such that, for every n≥ 1 and every function f:-1,1^n → ℝ Ebigl|f(x)-Ef(x)bigr| ≤ C_11aE|∇ f|(x), where x=(x_1,…,x_n) is uniform on -1,1^n and |∇ f|(x)=Bigl(Σ_j=1^n |D_j f(x)|^2Bigr)^1/2, D_j f(x)=f(x)-f(x^(j))/2, with x^(j)=(x_1,...,x_j-1,-x_j,x_j+1,...,x_n).
C_10 is the real Grothendieck constant K_G^ℝ. It is the smallest constant C such that for every m,n ≥ 1 and every real matrix A=(a_ij) ∈ ℝ^m× n one has max_substacku_1,…,u_m, v_1,…,v_n ∈ S^∞ Σ_i=1^m Σ_j=1^n a_ij ⟨ u_i, v_j⟩ ≤ C max_ε_1,…,ε_m, δ_1,…,δ_n = ± 1 Σ_i=1^m Σ_j=1^n a_ij ε_i δ_j.
Let X be a random vector in ℝ^n with an isotropic log-concave distribution (i.e. X has a log-concave density, E X=0, and Cov(X)=Id). Since X is isotropic, E|X|^2 = n.
The Gauss–Kuzmin–Wirsing (GKW) operator acts on suitable function spaces on [0,1] by (L f)(x) = Σ_k=1^∞ 1/(x+k)^2 f (1/x+k). This is the transfer operator of the Gauss map T(x) = \1/x\, which generates the continued fraction expansion.
