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.
196 shown· page 3 of 4
If n,m are natural numbers, let C(n,m) denote the maximum number of incidences that are possible between n points and m lines in the plane. Establish upper and lower bounds on C(n,m) that are as strong as possible.
Let f be a convex function with 1-Lipschitz gradient. We assume black-box access to the function and its gradient. Gradient descent will converge to a global minimum with an appropriate choice of _step size_ s: x_k+1 := x_k - s· ∇ f(x_k). In general, s can be chosen to vary with the step k.
C_39=H_3 is the Hadwiger covering number in dimension 3, which can also be formulated in terms of illumination of the boundary.
Let C denote the best constant for which | x: sup_h>0 1/2h ∫_x-h^x+h f(y) dy ≥ λ | ≤ C/λ ∫_ℝ f(x) dx for absolutely integrable non-negative f : ℝ → ℝ. What is C?
For 1 ≤ p ≤ 2, let C(p) be the best constant such that ‖ hat f ‖_L^p'(ℝ) ≤ C(p) ‖ f ‖_L^p(ℝ) holds for all test functions f : ℝ → ℝ. Here p' := p/p-1 is the dual exponent of p. What is C(p)?
For any n ≥ 3 and any convex body K in the plane, let C(n,K) be the largest quantity such that in every configuration of n points in K, there exists a triple of points determining a triangle of area at most C(n,K) times the area of K. Establish upper and lower bounds on C(n,K).
For any n ≥ 3 let C(n) be the largest quantity such that in every configuration of n points in the plane, there exists a triple of points determining a triangle of area at most C(n) times the area of their convex hull. Establish upper and lower bounds on C(n).
Let C be the best constant for which one has ‖f f‖_L^2(ℝ)^2 ≤ C ‖ff‖_L^1(ℝ) ‖f * f‖_L^∞(ℝ) for non-negative f : ℝ → ℝ. What is C?
C_33=A(2) is the Ihara constant over 𝔽_2. <a href="#DM2013-def-Aq">[DM2013-def-Aq]</a> For each integer g≥ 1, let N_2(g) := maxbigl\#X(𝔽_2) : X/𝔽_2 a smooth projective geometrically integral curve of genus gbigr. <a href="#DM2013-def-Nqg">[DM2013-def-Nqg]</a> Then A(2) := limsup_g→inftyN_2(g)/g.
Let G = (g_ij) be an M × N random matrix with independent standard Gaussian entries, and let Z(G) := | σ ∈ -1,1^N : G σ ≥ 0 coordinatewise |. This is the zero-margin binary (or Ising) perceptron. Write M = ⌊ α N ⌋. Define C_80 to be the infimum of all α > 0 such that ℙ(Z(G) > 0) → 0 as N → ∞.
Let d ≥ 1, and let q be a prime power. Let 𝔽_q be a finite field of order q. A Kakeya set is a set K that contains a line in every direction, and an Nikodym set N is a set with the property that every point x in 𝔽_q^d is contained in a line that is contained in N ∪ x.
Let n ≥ 2. Let C^T(n) denote the minimal area |bigcup_j=1^n T_j| of a union of triangles T_j with vertices (x_j,0), (x_j + 1/n, 0), (x_j + j/n, 1) for some real numbers x_1,…,x_n, and similarly define C^P(n) denote the minimal area |bigcup_j=1^n P_j| of a union of parallelograms P_j with vertices…
C_3b = SD(\0,1,∞\;-1) is the least exponent such that one has the inequality |A stackrelG- B| ≤ max(|A|, |B|, |A stackrelG+ B|)^C_3b whenever A, B are finite subsets of reals and G ⊂ A × B, where A stackrelG± B := a ± b: a ∈ A, b ∈ B.
C_24 is the Komlós discrepancy constant (often denoted K). For a real matrix A∈ℝ^m× n, define its (sign) discrepancy by disc(A) := min_x∈-1,1^n ‖Ax‖_∞. For each n≥ 1, define the dimension-n Komlós discrepancy K_n := supdisc(A): A∈ℝ^n× n and ‖A_ast j‖_2≤ 1 for all columns j.
Let D:=\z∈ℂ:lvert zrvert<1\. The Bergman space A^2(D) consists of analytic functions f on D with lVert frVert_2 := (1/π∫_D lvert f(z)rvert^2 dA(z))^1/2 < ∞, where dA(z) denotes the Lebesgue area measure. For c∈(0,1), write A(c,1) := z∈ℂ: c<lvert zrvert<1.
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 → ∞.
For positive-semidefinite d × d matrices A_1, …, A_n and any unitarily invariant norm |||·||| (including the operator norm and Schatten p-norms) and m ≤ n, define C(n,m,d) := inf frac 1/n^m Σ_j_1, j_2, …, j_m = 1^n |||A_j_1A_j_2… A_j_m||| (n-m)!/n! Σ_substackj_1, j_2, …, j_m = 1 \ all distinct^n…
Let n,d ≥ 2. Let C(d,n) denote the largest quantity such that, given any n distinct points x_1,…,x_n in R^d, the maximum distance max_1 ≤ i < j ≤ n ‖x_i-x_j‖ between the points is at least C(d,n) times the minimum distance min_1 ≤ i < j ≤ n ‖x_i-x_j‖. Establish upper and lower bounds for C(d,n).
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\).
For 0 ≤ ρ ≤ 1, let C(ρ) denote the largest quantity such that any graph on n vertices and (ρ+o(1)) C(n, 2) edges will have at least (C(ρ)-o(1)) C(n, 3) triangles. What is C(ρ)?
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.
For any n ≥ 1 and a geometric shape P (e.g. a polygon, a polytope or a sphere), let C(n, P) denote the smallest scale s such that one can place n identical copies of P with disjoint interiors inside another copy of P scaled up by a factor of s.
Is it possible for seven infinite circular cylinders C_1,…,C_7 of unit radius to touch all the others?
For any n ≥ 4, Let C(n) denote the maximum volume of a polyhedron with n vertices that all lie on the unit sphere S^2. What is C(n)? Which polyhedra attain the maximum volume?
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.
Let d ≥ 2 and D ≥ 1. For p ∈ 4,∞, let C^p(d,D) be the maximum of the ratio frac‖u‖_L^p(S^d)‖u‖_L^2(S^d) where u ranges over (real) spherical harmonics of degree D on the d-dimensional sphere S^d, which we normalize to have unit measure.
For each n ≥ 2, let C(n) be the smallest constant such that for any complex polynomial f of degree n ≥ 2 with zeros z_1, …, z_n in the unit disk and critical points w_1, …, w_n-1, and for any nonnegative weights l_1, …, l_n ≥ 0 satisfying Σ_k=1^n l_k = 1, we have min_1 ≤ j ≤ n-1 | Σ_k=1^n l_k z_k -…
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.
A graphon is a symmetric measurable function W : [0,1]^2 → [0,1]. Given a graphon W and a finite graph H = (V(H),E(H)), the homomorphism density t(H,W) is defined as t(H,W) = ∫_[0,1]^V(H) Π_v,w ∈ E(H) W(x_v,x_w) Π_v ∈ V(H) dx_v.
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].
