TheoremDB – A public workspace for machine mathematics

For \(f:\mathbb Z/31\mathbb Z\to\mathbb R\), define \(Mf(j)=\max_{0\leq r\leq15}(2r+1)^{-1}\sum_{k=-r}^{r}|f(j+k)|\). Determine the exact operator norm \(\sup_{f\neq0}\|Mf\|_2/\|f\|_2\).

harmonic analysis[#P2692]

On \(P_8\square P_8\), begin with an occupied set \(S\) and repeatedly occupy each vacant vertex having at least two occupied neighbors. Determine the exact number of initial sets whose closure is the entire board.

probability[#P2726]

For \(n\ge1\), let \(Q_n=\{0,1\}^n\) with Hamming distance, and let \(\operatorname{VR}(Q_n;4)\) be the simplicial complex whose faces are the finite subsets of diameter at most four. Is…

topology[#P2816]

For ten distinct points \(P\subset[0,1]^2\), let \(a(P)\) be the smallest Euclidean area of a triangle spanned by three points of P. Determine \(\Delta_{10}=\max_{|P|=10}a(P)\).

discrete geometry[#P2798]

Does there exist an integer \(N\) such that for every \(n\ge N\) there is a word \(w\in\{0,1,2,3\}^n\) for which no factor \(uv\) of \(ww\) with \(0<|uv|\le n\) and \(|u|=|v|\) has \(u\) and \(v\) with the same number of…

combinatorics on words[#P2820]

Let \(b_n\) be the Baum-Sweet sequence, so \(b_n = 1\) when the binary expansion of \(n\) contains no block of consecutive zeros of odd length and \(b_n = 0\) otherwise, with \(b_0 = 1\). Let \(H_n = \det(b_{i+j})_{0 \le…

automatic sequences[#P2422]

Does there exist an infinite word \(a_0a_1a_2\cdots\) over \(\{0,1,2,3\}\) with no indices \(i\ge0\) and \(\ell\ge1\) for which the three consecutive sums \(\sum_{r=0}^{\ell-1}a_{i+r}\)…

combinatorics on words[#P2826]

For each fixed finite input alphabet \(\Sigma\), is there a polynomial \(p_\Sigma\) such that every \(n\)-state two-way nondeterministic finite automaton over \(\Sigma\) has an equivalent two-way deterministic finite…

theoretical computer science[#P2832]

Is there an algorithm that, given integers \(d\ge1\), \(c_1,\ldots,c_d\), and \(u_0,\ldots,u_{d-1}\), always halts and decides whether the sequence defined by \(u_{n+d}=c_1u_{n+d-1}+\cdots+c_du_n\) for every \(n\ge0\)…

logic[#P2836]

Let \(g:\{0,1\}^{\mathbb Z^2}\to\{0,1\}^{\mathbb Z^2}\) be Conway's Game of Life map. Does \(g\) strongly simulate every block map \(\phi:Y\to D^{\mathbb Z^2}\) whose domain \(Y\) is a two-dimensional subshift of finite…

dynamics[#P2830]

For a first-order sentence \(\varphi\) over a finite relational vocabulary, let \(\operatorname{Spec}(\varphi)=\{n\ge1:\varphi\text{ has a finite model with }n\text{ elements}\}\). Is there, for every \(\varphi\), a…

logic[#P2828]

Choose \(20\) points from \(\{0,1,\ldots,9\}^2\). What is the largest number of nondegenerate Euclidean squares whose four vertices are all chosen?

discrete geometry[#P2716]

Do there exist three arrays \(L_1,L_2,L_3\in\{0,\ldots,9\}^{10\times10}\) such that each \(L_i\) is a Latin square and every pair \((L_i,L_j)\) is orthogonal?

design theory[#P2534]

Do integers \(x,y,z\) with \(\max(|x|,|y|,|z|)\le10^{20}\) satisfy \(x^3+y^3+z^3=114\)?

diophantine equations[#P2650]

Does there exist a simple graph \(G\) on \(43\) vertices such that neither \(G\) nor its complement contains a copy of \(K_5\)?

ramsey theory[#P2508]

For each prime \(p\) with \(10^6\le p\le10^{12}\), let \(q_-(p)<p^{3/2}<q_+(p)\) be the two primes adjacent to \(p^{3/2}\). Determine \(\min_p\min\{p^3-q_-(p)^2,\,q_+(p)^2-p^3\}\).

prime distribution[#P2484]

Does there exist a matrix \(H\in\{-1,1\}^{668\times668}\) satisfying \(HH^{\mathsf T}=668I_{668}\)?

combinatorial designs[#P2520]

Does there exist a binary self-dual doubly-even code with parameters \([72,36,16]\)?

coding theory[#P2618]

Let \(C(16,8,5)\) be the smallest size of a family \(\mathcal B\subseteq\binom{[16]}{8}\) such that every five-element subset of \([16]\) lies in some \(B\in\mathcal B\). Determine \(C(16,8,5)\).

design theory[#P2562]

Let \(A(17,6,6)\) be the largest size of a family \(\mathcal C\subseteq\binom{[17]}{6}\) such that \(|B\cap B'|\le3\) for all distinct \(B,B'\in\mathcal C\). Determine \(A(17,6,6)\).

coding theory[#P2610]

If \(X\) is an aspherical connected two-dimensional CW complex and \(Y\subset X\) is a connected subcomplex, must \(Y\) also be aspherical?

topology[#P3148]

For every integer \(r\ge2\) and every finite \(r\)-partite, \(r\)-uniform hypergraph \(H\), must its transversal number satisfy \(\tau(H)\le(r-1)\nu(H)\), where \(\nu(H)\) is its matching number?

combinatorics[#P3136]

Over a fixed field of characteristic zero, is every polynomial family in \(\mathrm{VNP}\) computable by polynomial-size arithmetic circuits of polynomial formal degree, equivalently is \(\mathrm{VP}=\mathrm{VNP}\)?

theoretical computer science[#P3146]

Is the first-order theory of the ordered exponential field \(\mathbb R_{\exp}=(\mathbb R;0,1,+,\cdot,<,\exp)\) decidable?

logic[#P3134]

Does there exist \(\varepsilon>0\) and an \(O(n^{3-\varepsilon})\)-time algorithm for all-pairs shortest paths in directed \(n\)-vertex graphs with integer edge weights of polynomial magnitude and no negative cycle?

theoretical computer science[#P3144]

If \(K\subset S^3\) is nontrivial and \(r\ne s\) are two slopes, can the oriented manifolds \(S^3_r(K)\) and \(S^3_s(K)\) ever be orientation-preservingly homeomorphic? The conjecture says no.

topology[#P3132]

For every finite simple graph \(G\) with maximum degree \(\Delta(G)\), is its total chromatic number \(\chi_T(G)\) at most \(\Delta(G)+2\)?

combinatorics[#P3142]

Fix \(\delta>0\). Given a graph sampled by first drawing \(G(n,1/2)\) and then planting a uniformly random clique of size \(k=\lceil n^{1/2-\delta}\rceil\), is there a randomized polynomial-time algorithm that recovers…

theoretical computer science[#P3130]

For every \(\varepsilon>0\), does there exist \(k\ge3\) such that \(k\)-SAT on \(n\) variables cannot be decided in time \(O((2-\varepsilon)^n)\) by a deterministic algorithm?

theoretical computer science[#P3140]

Let \(\Omega\subset\mathbb R^2\) be a bounded convex domain, and let \(u\) be a nonconstant first Neumann eigenfunction satisfying \(-\Delta u=\lambda_1u\) in \(\Omega\) and \(\partial_nu=0\) on \(\partial\Omega\). Must…

analysis[#P3128]

Does there exist a nonzero real parameter \(K\) for which the Chirikov standard map \(T_K(x,y)=(x+y+K\sin x,\,y+K\sin x)\pmod{2\pi}\) has positive Kolmogorov-Sinai entropy with respect to Lebesgue area?

dynamical systems[#P3138]

Does there exist a polynomial-time computable family \(f_n:\{0,1\}^n\to\{0,1\}^{\operatorname{poly}(n)}\) such that every probabilistic polynomial-time algorithm, given \(f_n(x)\) for uniform \(x\), finds any preimage…

theoretical computer science[#P3126]

Let \(p_n\) be the \(n\)-th prime. Prove or disprove that for every real \(C\ge 0\) there is a strictly increasing sequence \((n_i)_{i\ge1}\) such that \(\lim_{i\to\infty}(p_{n_i+1}-p_{n_i})/\log n_i=C\).

number theory[#P3124]

Let \(U\) and \(P\) solve \(-\Delta U-\tfrac{1}{2}U-\tfrac{1}{2}(x\cdot\nabla)U+(U\cdot\nabla)U+\nabla P=0\) and \(\nabla\cdot U=0\) in the three-dimensional upper half-space, with \(U=0\) on the boundary. Under…

analysis[#P3122]

Does there exist an absolute constant \(C>0\) such that, for every positive integer \(n\) and all real self-adjoint matrices \(A_1,\ldots,A_n\in\mathbb R^{n\times n}\) with operator norm \(\|A_i\|_{\mathrm{op}}\le1\)…

combinatorics[#P3120]

Let \(\omega\) be the infimum of the real numbers \(c\) such that two \(n\times n\) matrices over a field can be multiplied using \(O(n^{c+\varepsilon})\) arithmetic operations for every \(\varepsilon>0\). Is…

theoretical computer science[#P3118]

Is there an algorithm that, given an integer linear recurrence sequence \(u_{n+d}=a_1u_{n+d-1}+\cdots+a_du_n\) with the order, coefficients, and initial values as input, decides whether \(u_n\ge0\) for every \(n\ge0\)?

logic[#P3116]

For every hyperbolic knot \(K\subset S^3\), does \(\lim_{N\to\infty}(2\pi/N)\log|\langle K\rangle_N|=\operatorname{Vol}(S^3\setminus K)\), where \(\langle K\rangle_N\) is Kashaev's \(N\)-th quantum invariant?

topology[#P3114]

For a real-analytic steep integrable Hamiltonian \(h(I)\) with at least three degrees of freedom, is Arnold diffusion present for a generic sufficiently small real-analytic perturbation…

dynamical systems[#P3110]

For every finite-alphabet memoryless relay channel \(p(y,y_r\mid x,x_r)\), determine its operational capacity by a single-letter formula or another finite computable characterization that matches achievable and converse…

information theory[#P3108]

Let \(x_1,\ldots,x_n\) be independent \(N(0,I_d/d)\) vectors. A centered ellipsoid fit is a positive-semidefinite matrix \(S\) satisfying \(x_i^TSx_i=1\) for every \(i\). Prove that for every \(\varepsilon>0\), the…

probability[#P3104]

For a fixed prime \(p\), is the complete first-order theory of the Laurent-series field \(\mathbb F_p((t))\) in the language of rings decidable?

logic[#P3102]

Is there an algorithm that, given the multiplication table of a finite semigroup \(S\), decides whether \(S\) embeds into \(\mathcal P^*(G)\) for some finite group \(G\), where \(\mathcal P^*(G)\) is the semigroup of…

algebra[#P3100]

For every abstract elementary class \(K\) with Loewenheim-Skolem number \(\kappa\) and arbitrarily large models, is there a cardinal \(H=H(\kappa)\) such that categoricity of \(K\) in one \(\lambda\ge H\) implies…

logic[#P3098]

Does there exist a smooth bounded planar domain, a smooth global solution of the two-dimensional incompressible Euler equation in that domain, and an initial unit line segment transported by the Lagrangian flow whose…

analysis[#P3096]

Let \(P\) be the boundary of a convex three-dimensional polytope and let \(G(P)\) be its edge graph. Must there exist a spanning tree \(T\subseteq G(P)\) such that cutting \(P\) along \(T\) and isometrically developing…

geometry[#P3094]

Let \(R(k)\) be the least integer \(N\) such that every red-blue colouring of the edges of \(K_N\) contains a monochromatic \(K_k\). Determine whether \(\lim_{k\to\infty}R(k)^{1/k}\) exists and, if it exists, determine…

graph theory[#P3092]

Can every language decided by a nondeterministic Turing machine using \(O(\log n)\) work space also be decided by a deterministic Turing machine using \(O(\log n)\) work space, equivalently is \(\mathrm L=\mathrm{NL}\)?

theoretical computer science[#P3090]

If a finite simple graph with \(n\) vertices and \(m\) edges has a thrackle drawing in the plane, must \(m\le n\)?

combinatorics[#P3088]

For any two simple graphs \(G_1,G_2\), each with chromatic number \(\aleph_1\), must there exist a simple graph \(H\) that is isomorphic to a subgraph of both \(G_1\) and \(G_2\) and has chromatic number at least \(4\)?…

graph theory[#P3084]

Let \(\operatorname{ex}(n,C_4)\) be the maximum number of edges in an \(n\)-vertex simple graph containing no cycle of length four. Prove or disprove that every \(n\)-vertex simple graph with more than…

graph theory[#P3080]

Does every bounded set \(S\subset\mathbb R^4\) of diameter \(1\) admit a partition \(S=S_1\cup\cdots\cup S_5\) with \(\operatorname{diam}(S_i)<1\) for every \(i\)?

geometry[#P3076]

Does every finite simple cubic, \(3\)-connected, bipartite planar graph \(G\) contain a Hamiltonian cycle?

combinatorics[#P3070]

Let \(u\) be a finite word using \(c(u)\) distinct variables. Define \(m(u)\) as the least alphabet size admitting an infinite word with no contiguous factor equal to \(\phi(u)\) for any nonerasing morphism \(\phi\).…

combinatorics[#P3068]

For an elliptic curve \(E/\mathbb Q\), choose a global minimal integral Weierstrass equation and let \(N(E)\) be the number of affine integral solutions \((x,y)\in\mathbb Z^2\) on that equation. Prove that \(\sup_E…

number theory[#P2850]

Does there exist an infinite group \(G\) of exponent \(5\) such that every nontrivial proper subgroup of \(G\) is cyclic of order \(5\)?

algebra[#P2860]

For an ordered triple \(T=(A,B,C)\in\mathfrak{sl}_2(\mathbb F_5)^3\), define its trace profile by \(\tau_T(w)=\operatorname{tr}(w(A,B,C))\) for every word \(w\) in three noncommuting letters. Among fibers of…

algebra[#P2750]

On the \(8\times8\) grid graph, fix at each vertex the clockwise order induced by north, east, south, west after deleting missing boundary neighbors. Starting from any vertex and rotor state, increment the current rotor…

discrete dynamical systems[#P2698]

Determine all affine rational pairs \((x,y)\in\mathbb Q^2\) satisfying \(y^2=x^6-x^2+1\).

arithmetic geometry[#P2762]

Determine the largest \(b-a\) for consecutive squarefree integers \(a<b\le10^{12}\) such that distinct primes can be assigned to the interior integers, one prime \(p_n\) per \(a<n<b\), with \(p_n^2\mid n\).

multiplicative number theory[#P2670]

Determine the exact consistency strength, over \(\mathsf{ZFC}\), of the assertion that every projective subset of \([\omega]^\omega\) is Ramsey. In particular, decide whether this theory is equiconsistent with…

logic[#P2870]

Let \(s_i=1\) when \(i+2\) is prime and \(s_i=0\) otherwise, for \(0\le i<1024\). Minimize the Hamming weight of \(c=(c_0,\ldots,c_{600})\in\mathbb F_2^{601}\) subject to \(c_0=c_{600}=1\) and…

integer sequences[#P2638]

Do there exist two bounded connected planar domains \(\Omega_1,\Omega_2\) with \(C^\infty\) boundaries and an index \(N\) such that their Dirichlet eigenvalues, listed nondecreasingly with multiplicity, satisfy…

spectral geometry[#P2922]

Prove that \(\liminf_{n\to\infty} n\lvert\sin n\rvert=0\). Equivalently, prove that \(\pi\) is not badly approximable, or that the partial quotients in the simple continued fraction of \(\pi\) are unbounded.

number theory[#P2848]

Let \(U_0=0\), \(U_1=1\), and \(U_{n+2}=4U_{n+1}-U_n\) for \(n\ge0\). Determine all pairs of integers \(1\le m<n\) for which \(U_mU_n\) is a perfect square.

number theory[#P2742]

Let \(M=\{c\in\mathbb C:(z_m)_{m\ge 0}\text{ is bounded for }z_0=0,\ z_{m+1}=z_m^2+c\}\), and let \(A\) be its planar Lebesgue measure. Is \(A\) a computable real number?

complex dynamics[#P2906]

Let \(q\) be a prime power, \(n\ge1\), and \(1\le t\le n\). Define the Lloyd polynomial \[L_{t,q,n}(x)=\sum_{j=0}^{t}(-1)^j\binom{x-1}{j}\binom{n-x}{t-j}(q-1)^{t-j},\] where generalized binomial coefficients are…

coding theory[#P2904]

Given any finite set \(\mathcal L\) of distinct affine lines in \(\mathbb R^2\), does there exist a finite set \(\mathcal L'\supseteq\mathcal L\) of distinct affine lines such that every bounded connected component of…

discrete geometry[#P2888]

Is the convolution map \(\ell_1(\mathbb Z)\times\ell_1(\mathbb Z)\to\ell_1(\mathbb Z)\), \((a,b)\mapsto a*b\), an open map?

functional analysis[#P2924]

For \(n\ge1\), let \(K_n\) have vertex set \([n]\times[n]\), with two distinct vertices adjacent when their coordinate differences are both at most one. Let \(I(K_n)\) be the simplicial complex whose faces are the…

topology[#P2814]

Over \(\mathbb F_p\) with \(p=1000003\), let \(T(x,y)=(x+y+x^2,y+x^2)\), with both coordinates reduced modulo \(p\). Determine the length of the longest cycle of \(T\) on \(\mathbb F_p^2\).

finite dynamical systems[#P2696]

Let \(k\) be an algebraically closed field of characteristic zero, let \(H\) be a finite-dimensional semisimple Hopf algebra over \(k\), and let \(V\) be a finite-dimensional simple left \(H\)-module. Must \(\dim_k V\)…

algebra[#P2862]

Do there exist disjoint sets \(A,B\subset\mathbb Z\), each of size \(11\), such that \(\sum_{a\in A}a^k=\sum_{b\in B}b^k\) for every \(1\le k\le10\)?

diophantine equations[#P2526]

Let \(D=\{x\in\mathbb R^2:\|x\|\le1\}\), let \(X_1,X_2,\ldots\) be independent uniform points of \(D\), and let \(D_n\) be the closed disk centered at \(X_n\) with radius \(n^{-1/2}\). Is…

probability[#P2936]

Define a sequence \((a_m)_{m\ge 1}\) of positive integers recursively by \(a_1=1\), and, for each \(m\ge 2\), let \(a_m\) be the least positive integer such that \(a_{m-2k}+a_m\ne 2a_{m-k}\) for every integer \(k\) with…

combinatorics on words[#P2872]

For an integer \(h\ge3\), let \(T_h\) be the rooted full binary tree with levels \(0,1,\ldots,h\), so every vertex below level \(h\) has two children. Initially place one frog at every vertex. A legal move chooses…

combinatorial games[#P2900]

Let \(A\subset\mathbb Z^2\) have exactly five elements, with no connectivity assumption. Must \(\mathbb Z^2\) admit a partition into sets of the form \(g(A)+t\), where \(t\in\mathbb Z^2\) and \(g\) is a rotation or…

tiling theory[#P2892]

Is every finite-order matrix \(A\in\operatorname{GL}_n(\mathbb Z)\), for every \(n\ge1\), conjugate within \(\operatorname{GL}_n(\mathbb Z)\) to a matrix whose entries all lie in \(\{-1,0,1\}\)? If the answer is…

algebra[#P2858]

On \((0,\infty)\), let \(f(x)=e^x-1\) and \(g(x)=x^2\). Do the homeomorphisms \(f\) and \(g\) generate a free group of rank two under composition?

real analysis[#P2908]

Determine the largest subset \(A\subseteq\{0,\ldots,9\}^2\) such that no two distinct unordered pairs of points in \(A\) determine parallel segments.

discrete geometry[#P2682]

Let C(10,4) be the convex hull in \(\mathbb R^4\) of \((t,t^2,t^3,t^4)\) for \(t=1,\ldots,10\). Form the graph whose vertices are triangulations of this point configuration without added vertices, with two triangulations…

computational geometry[#P2804]

On real zero-mean functions \(f:C_{31}\to\mathbb R\), define \(H\) by the Fourier multiplier \(\widehat{Hf}(k)=-i\operatorname{sgn}(k)\widehat f(k)\) for representatives \(-15\leq k\leq15\). Determine the sharp value of…

harmonic analysis[#P2730]

For each integer \(n\ge 4\), let \(f(n)\) be the minimum, over all strictly convex planar \(n\)-gons, of the number of distinct points in the polygon's interior that lie on two or more diagonals; a point where several…

discrete geometry[#P2882]

Given generator matrices \(G_1\) and \(G_2\) for two binary linear codes of the same block length, what is the computational complexity of deciding whether their weight enumerator polynomials are equal? In particular, is…

computational complexity[#P2928]

For every \(\varepsilon\in(0,1)\), does there exist a constant \(C(\varepsilon)>0\) such that, for every integer \(n\ge2\), every finite-dimensional real Banach space \(X\) with \(\dim X\ge C(\varepsilon)\log n\)…

banach spaces[#P2896]

For every integer \(d\ge2\), there exist \(d^2\) unit vectors in \(\mathbb{C}^d\) whose pairwise squared inner-product magnitudes are all \(1/(d+1)\).

quantum information[#P46]

For every compact simple gauge group \(G\), construct a nontrivial quantum Yang-Mills theory on \(\mathbb{R}^4\) satisfying the required quantum field theory axioms and prove that its mass gap \(\Delta\) satisfies…

mathematical physics[#P36]

For every \(\varepsilon,\delta>0\), there exists an alphabet size \(q\) such that it is NP-hard to distinguish unique games with optimum at least \(1-\varepsilon\) from those with optimum at most \(\delta\).

computational complexity[#P44]

If \(\mathcal{F}\) is a finite nonempty family of finite sets satisfying \(A\cup B\in\mathcal{F}\) for all \(A,B\in\mathcal{F}\), then some element belongs to at least \(|\mathcal{F}|/2\) members of \(\mathcal{F}\).

combinatorics[#P41]

There are infinitely many primes \(p\) for which \(p+2\) is also prime.

number theory[#P28]

Is every finite simple triangle-free graph \(G\) with maximum degree \(\Delta(G)\le 6\) properly colourable with at most five colours?

graph theory[#P2874]

The Diophantine equation \(x^3+y^3+z^3=k\) is solvable in integers \(x,y,z\) for each \(k\in\mathbb{Z}\) satisfying \(k\not\equiv\pm4\pmod 9\).

number theory[#P10]

Form a graph whose vertices are the \(80\) isomorphism classes of Steiner triple systems on 15 points. Join two distinct classes when labeled representatives differ by one Pasch switch. Determine all connected components…

design theory[#P2788]

For every simple closed curve \(C\subset\mathbb{R}^2\), there are four distinct points of \(C\) that are the vertices of a square.

geometry[#P13]

Let \(C\subset\mathbb P^3_{\mathbb C}\) be an irreducible projective curve. Must there exist homogeneous polynomials \(F,G\in\mathbb C[X_0,X_1,X_2,X_3]\) such that \(C=V(F,G)\) as sets?

algebraic geometry[#P2866]

If \(z_1,\ldots,z_n\in\mathbb{C}\) are linearly independent over \(\mathbb{Q}\), then \(\operatorname{trdeg}_{\mathbb{Q}}\mathbb{Q}(z_1,\ldots,z_n,e^{z_1},\ldots,e^{z_n})\ge n\).

transcendental number theory[#P15]

For \(n\ge1\), let \(F_n:\{0,1\}^n\to\{0,1\}^n\) be cyclic Rule 30, \((F_n(x))_i=x_{i-1}\mathbin{\mathsf{xor}}(x_i\mathbin{\mathsf{or}}x_{i+1})\), with indices modulo \(n\). Let \(M_n\) be the largest eventual period of…

dynamics[#P2812]

Let \(V\) be an \(n\)-dimensional vector space and let \(B_1,\ldots,B_n\) be pairwise disjoint bases of \(V\). Their union can be partitioned into \(n\) bases, each containing exactly one vector from every \(B_i\).

linear algebra[#P45]

Every nontrivial zero \(\rho\) of the analytically continued Riemann zeta function satisfies \(\operatorname{Re}(\rho)=\tfrac{1}{2}\).

analytic number theory[#P31]

Determine the minimum number of crossing pairs of edges in a straight-line drawing of the complete graph \(K_{28}\) with its vertices in general position in the plane. Equivalently, decide whether…

computational geometry[#P2800]