Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A paper torus is an embedded polyhedral torus isometric to a flat torus. Schwartz proves no paper torus with 7 vertices exists and constructs one with 8, settling the minimum-vertex question in the flat-torus embedding tradition of…
Kac's walk on the rotation group, introduced by Hastings in 1970, is a central high-dimensional Markov chain in statistical physics and computational science. The paper proves it mixes in n^2 log n steps, the conjectured optimal rate,…
Given a binary matrix M, decide whether its columns can be permuted so that every row contains at most two blocks of 1s and, if it contains two blocks, they are separated by at most one 0. The claimed theorem proves that this (2,1)-Gapped…
Zhi-Wei Sun conjectured a closed evaluation of a truncated Legendre-symbol determinant. For every prime p ≡ 3 pmod 4 it equals ⌊ (p-2)/3 ⌋^2 x, proved by reducing to inverse data for Chapman's full Legendre-symbol matrix and evaluating…
For an irreducible crystallographic root system of rank r with Coxeter number h, the paper proves that Au's normalized Witten zeta function has a simple pole at 2/h and evaluates its residue in closed form in terms of the Cartan…
If a chromatic symmetric function is Schur positive, must every finite-variable specialization X_G(x_1, …, x_k) have a saturated Newton polytope? A 12-vertex bipartite graph realizes weights (6,6,0) and (8,2,2) but omits their midpoint…
For n ≥ 4, the natural scalar Poisson-summation certificates cannot prove the Regev-Stephens-Davidowitz Gaussian mass conjecture: any such certificate saturates, so the whole approach is blocked.
For P_n(z) = ∑_k=0^n ε_k z^k with independent uniform signs, does the number R_n of roots in |z| ≤ 1 satisfy R_n/(n/2) → 1 almost surely? The manuscript proves the strong law with R_n = n/2 + O_ω(n^149/150).
Chromatic quasisymmetric functions of natural unit interval graphs were conjectured to have log-concave coefficients in the elementary basis. A connected 13-vertex example refutes it: for the Hessenberg function…
For deterministically minimizing a convex 1-Lipschitz function on the d-dimensional ball using only exact function values, the query complexity sat between Ω(d) and O(d^2 log^2 d) since 1996. The paper proves a near-quadratic lower bound…
Can the k-distinct language - words over [n] of length at most k with no repeated symbol - be recognized by an acyclic NFA of size c^k n^O(1) for some c < 4? A construction of size 2^1.96992k n^O(1) < 3.918^k n^O(1) answers yes.
Erdos and Hajnal asked whether h_r(G) = maxχ(H) : H ⊆ G, girth(H) ≥ r tends to infinity as χ(G) does, for every fixed r ≥ 4. It does in every fixed polynomial edge-density regime.
A subset A of the pointwise-ordered cube [0,1]^n is a k-antichain when it meets every chain in at most k points. The conjecture concerns the largest possible (n-1)-dimensional Hausdorff measure of such a set; it is settled here, following…
The Huneke–Wiegand Conjecture: Let R be a one-dimensional Gorenstein local domain, and let M be a finitely generated, non-zero, torsion-free R-module. If the tensor product M ⊗_R M^* is torsion-free, then M is a projective (hence free)…
For an arrangement of n hyperplanes in P^3_C with ℓ intersection lines and p intersection points where at least three hyperplanes meet, the refined form of Purdy's inequality expects p - ℓ + n + 2 ≥ 0. An explicit arrangement built from…
How many nondegenerate equilibrium points can the potential of three positive point charges have? Gabrielov, Novikov and Shapiro had proved at most 12, and observed that their method would give 6 if an auxiliary polynomial system had at…
Does every instance of indivisible goods with additive valuations admit a balanced allocation (any two bundles differing in size by at most one) that is simultaneously envy-free up to one good (EF1) and fractionally Pareto optimal (fPO)?…
Aldroubi, Cabrelli, Krishtal and Molter conjectured that for a bounded normal operator T and any vector g, the normalized orbit T^k g / |T^k g| : k ≥ 0 is never a frame. It can be: an explicit construction produces a normalized orbit that…
Kotzig conjectured that for every even n ≥ 4 the complete graph K_n decomposes into n-1 perfect matchings such that every pair of them forms a Hamilton cycle. An asymptotic version holds: K_n decomposes into n-1 perfect matchings of which…
Simon conjectured that every skeleton of a simplex is extendably shellable. False: for every d ≥ 3 there is a pure d-dimensional shellable simplicial complex that is not shelling completable.