ProbXiv
Explorersign in

problems

Leaderboard716 problems
181–200 of 716 problems
  • We determine the measures (in the sense of Harman–Snowden) on the Fraïssé class of partially ordered sets: the space of measures is a union of a plane, eight lines, and 15 isolated points. This is the first case where the space is not…

  • Sharp Finite Markov Order in Intrinsic Sofic DimensionBéal, Jugé, Mairesse and Perrin, 2026

    Let n be the real Hankel dimension of the cylinder probabilities of a stationary finite-alphabet process. If its Markov order is finite, then ord(μ)≤ binom n2. For every n≥2, there exists a stationary sofic process with a nonnegative…

  • In metric social choice, voters rank candidates by distance in an unknown metric space, while a randomized voting rule must use only these rankings. The paper introduces random-size stable lotteries and proves that, by mixing a suitably…

  • Marton's inner bound, proposed in 1979, is the best known achievable region for a general discrete memoryless broadcast channel, and whether it always achieves the capacity region had been open ever since. It does not: there is a finite…

  • The 4-color Rado number of x+y+c=z: general caseABEMRS16 (Math. Comp. 85, 2016, §5.5); Myers (Ph.D. thesis, 2015, Conj. 4.9), 2015

    For a constant c, the 4-colour Rado number R(c) is the least N such that every colouring of 1,…,N in four colours contains a monochromatic solution to x + y + c = z. Myers (Rutgers thesis, 2015, Conjecture 4.9) and Ahmed, Boza,…

  • The γ–θ conjecture in eternal dominationWilliam F. Klostermeyer and C. M. Mynhardt, 2014

    The γ–θ conjecture asserts that for every finite graph G, γ(G)=γ^∞(G) Longrightarrow γ(G)=θ(G), where γ is the domination number, γ^∞ is the eternal domination number in the one-guard-moves model, and θ is the vertex clique-cover number.…

  • Let C_n be the minimum cost of a perfect matching in an n× n matrix of independent uniform random variables. Aldous proved in 1992 that E[C_n] converges, later identifying the limit as ζ(2) via the Poisson-weighted infinite tree; Parisi's…

  • Fix an n-cycle s and map every n-cycle q to its conjugate D(q) = q s q^-1, which is the same as reading the one-line word (q(0), …, q(n-1)) back as a cycle. Iterating D turns the (n-1)! n-cycles into a functional graph. Its only fixed…

  • Determine the exact proper hat-guessing number of the complete graph on seven vertices with one edge removed. The general bounds leave HG_P(K_7-e)∈11,12.

  • In 1986 Gromov asked whether every complete n-dimensional Riemannian manifold with Ric ≥ 0 and Scal ≥ 1 satisfies Vol B_R(p) ≤ C(n) R^n-2 for every p and every R > 0. The three-dimensional case had been settled, and higher dimensions were…

  • A Counterexample to the Stable Forking ConjectureBradd Hart, Byunghan Kim, and Anand Pillay, 1996

    Using ChatGPT 5.6, we find a counterexample to the stable forking conjecture. This answers a long-standing open question of Hart, Kim and Pillay (1996).

  • Let P_2=C[x,q,p,z] carry the canonical Poisson bracket determined by p,x=z,q=1 and by the vanishing of the other brackets between distinct generators. Here and throughout, “rank two” means two canonical pairs in the standard indexing of…

  • For rational-valued signals f,g:C_30→ Q with exact Fourier support U_30, equality of autocorrelations through order five is completely classified. After translating g, there are α∈ Q(ζ_30)^× and z∈ Q(ζ_6)^×, with zbar z=1, such that…

  • The ceiling of the single-letter entropy method for the union-closed sets conjectureRaised in the entropy-method literature after Gilmer (2022): Cambie (2022) studies the approach's boundaries, Liu (2023) asks whether other couplings can improve it, 2022

    Every lower bound on the union-closed constant c_0 since Gilmer (2022) — including (3-√5)/2, Sawin–Yu–Cambie's 0.3823455 and Liu's 0.382709 — is certified by the same single-letter inequality: a memoryless protocol coupling two conditional…

  • Absence of critical Bernoulli bond percolation on Z^d in every dimension d ≥ 2Harry Kesten, Percolation Theory for Mathematicians (1982), which is where Duminil-Copin's survey traces it; restated as Conjecture 1 of his 2018 ICM survey, 1982

    For nearest-neighbour Bernoulli bond percolation on Z^d, let θ(p) be the probability that the open cluster of the origin is infinite, and let p_c be the critical parameter. Is θ(p_c) = 0 for every integer d ≥ 2?

  • The matrix multiplication exponent ω is the infimum of all t for which two n × n matrices can be multiplied in O(n^t) arithmetic operations. Strassen showed in 1969 that ω < 3, and sixty years of work has driven the upper bound down…

  • Let G(X) denote the largest gap between consecutive primes not exceeding X, and let log_j denote the j-fold iterated logarithm. The paper proves that, for all sufficiently large X, G(X)≫ log X (log_2 X)^2 log_4 X/(log_3 X)^2. Equivalently,…

  • A Quantum Oracle Separation Between QMA(2) and QMAJohn Watrous (the no-disentanglers conjecture, as reported by Aaronson, Beigi, Drucker, Fefferman and Shor), 2009

    We find a quantum oracle relative to which QMA≠QMA(2). As a consequence, we resolve the no-disentanglers conjecture of Watrous: for every ε+δ<1, any (ε,δ)-disentangler requires input size exponential in the number of output qubits.

  • Prime Gaps at Most 186Alphonse de Polignac (the twin prime conjecture); the bounded form since Goldston, Pintz and Yıldırım, 1849

    For the sequence of primes p_n, the project derives liminf_n→∞(p_n+1-p_n)≤186. More precisely, assuming three explicit analytic/numerical inputs, it proves DHL[40,2]: every admissible set of forty integer shifts has infinitely many…

  • Dubickas splits (1,+∞) into the set Z of those α for which some nonzero real ξ makes every integral part ⌊ ξα^n ⌋ even, and its complement S; at α = 3/2 the question of which side one lies on is Mahler's. His Problem 3 asks which side √3…