Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
Englert and Rehacek conjectured which measurement is globally information-optimal for an ensemble of equiangular equiprobable pure states. Their conjecture holds, via the remaining entropy inequalities of Holevo and Utkin.
Can an S-decoding polynomial modulo a suitable product of k primes attain the lower-bound minimum of k + 1 nonzero coefficients? A construction matches the bound for special products of k primes, yielding exponentially fewer-server PIR.
Dittert's conjecture asserts that among nonnegative n× n matrices whose entries sum to n, the functional φ(A)=∏_i r_i+∏_j c_j-per(A) is uniquely maximized by J_n/n. The paper proves the case n=16 which, with Pang's result for n≥17,…
Does there exist a good pairwise-coprime sequence u_n with ∑ 1/u_n < ∞ and polynomial growth? What if one only requires u_n ≤ e^o(n)?
Anari, Charikar and Ramakrishnan asked whether every fractional perfect matching admits a perfect matching that is α-thin with respect to it, meaning it crosses every cut at most α times the fractional amount. Resolved up to…
For every connected graph, is the deviation of its adjacency eigenvalues at most its order divided by its average distance? Exact lollipop-graph certificates refute the inequality when deviation means population standard deviation, under…
An ℓ-Oddtown is a family of subsets of an n-element set whose set sizes are not divisible by ℓ while all pairwise intersection sizes are. Berlekamp and Graver showed the maximum size is n for prime ℓ, Babai and Frankl extended this to…
A tournament orients every pair in a round-robin (winner → loser). The score sequence is the sorted win-count list. Reversing a directed 3-cycle never changes scores, so score-equivalent tournaments can look structurally different.…
Do n point charges whose electrostatic potential has only non-degenerate critical points always have at most (n-1)^2 of them? A configuration of five charges - three at the vertices of an equilateral triangle plus two small central charges…
Godara and Sarkar proved d(H_27)=6 for the exponent-p Heisenberg group and posed d(H_p^3)=3p-3 for every odd prime p, leaving p≥5 open. The paper settles the first open case, d(H_125)=12, the upper bound reducing to a finite spread bound…
The paper constructs an exact cluster F⊆Z^2 of cardinality 8 with full affine span and an F-tiling whose orbit closure contains no 1-periodic F-tiling, giving a non-degenerate counterexample to Nivat's conjecture for non-convex windows.…
For an odd prime p, do Sun's normalized trigonometric permanents satisfy s_p < 0 ⇔ p ≡ 5 pmod12 and s'_p < 0 ⇔ p ≡ 7 pmod 8? Exact computation at p = 29 refutes both sign laws.
For a projective variety X with at worst Gorenstein canonical singularities whose stringy E-function E_st(X; u, v) is a polynomial, all stringy Hodge numbers h^p,q_st(X) are non-negative. (Batyrev 1998, Conjecture 3.10.)
We prove that every PPT linear map has finite entanglement-breaking index, thereby establishing the eventual entanglement-breaking property of PPT channels in full generality. Furthermore, by utilizing completely positive maps with low…
The target-free clique conjecture asserts that the supports of stable fixed points of a nondegenerate combinatorial threshold-linear network are exactly its target-free cliques, the bidirected cliques no outside vertex receives an edge…
Energy measures of any two nonconstant harmonic functions on the standard Sierpinski gasket are mutually absolutely continuous. Strichartz and Tse reported numerical evidence that the Radon-Nikodym densities are L^p-integrable for 1 < p <…
R(c) = 40c+41 for every c ≥ 2 such that c+1 is divisible by 3, 4, 5, or 7 (covering ≈ 66% of all c); the full conjecture (Myers 2015 Conj. 4.9, ABEMRS16 §5.5) reduces to prime cases p ≥ 89, all smaller primes settled by SAT. Twenty-eight…
Does planarity help approximate counting? The paper gives an FPRAS for the planar hard-core partition function at small activity, proves that approximately counting q-colourings on planar graphs is NP-hard for every constant q ≥ 4, and…
Sampling a nearly uniform Eulerian tour of a directed Eulerian multigraph was stuck at mn-type running times coming from arborescence sampling. A randomized algorithm achieves widetildeO(m^3/2) worst case, breaking that barrier on sparse…