Mathematics Problem Archive

Let $M(n)$ be the number of monotone Boolean functions of $n$ variables, equivalently the number of antichains of subsets of an $n$-element set. Deter...

Let $f$ be entire and suppose every zero of every derivative $f^{(n)}$, $n\ge0$, lies in the closed lower half-plane. Must $f$ lie in the compact-open...

For a regular connected compact plane set $E$, let $\beta_E=\limsup_{\varepsilon\to0}\log l(\varepsilon)/(-\log\varepsilon)$, where $l(\varepsilon)$ i...

For real matrices $A\in\operatorname{Mat}_{n\times n}$, $B\in\operatorname{Mat}_{n\times p}$, and $C\in\operatorname{Mat}_{m\times n}$ with $n=mp$, de...

Determine the least number of colors needed to color the Euclidean plane so that points at unit distance receive different colors....

Given a finite planar point set and a prescribed rectangle, approximate efficiently the minimum number of congruent copies of the rectangle needed to ...

Can the $3\times6$ rectangle with a $2\times2$ corner removed tile a rectangle using an odd number of congruent copies?...

Can sums of square roots of integers be compared in polynomial time on a Turing machine? Equivalently, obtain effective polynomial bit bounds for a no...

Find the largest function $t(n)$ such that every convex $n$-gon has a triangulation containing at least $t(n)$ distinct triangle areas; also determine...

Are there quasiperiodic global minimals for metrics on the torus that are close to a flat three-dimensional torus? Here a geodesic is a global minimal...

Characterize mixing shifts of finite type up to topological orbit equivalence....

If a nonnegative integer matrix $A$ has a unique, simple, nonzero eigenvalue $n$, prove that $A$ is strong shift equivalent over $\mathbb Z_+$ to the ...

Classify shifts of finite type up to topological conjugacy; in particular, give a decision procedure determining whether two nonnegative integer matri...

Given a mixing shift of finite type $S_A$, determine the range of the dimension representation $\operatorname{Aut}(S_A)\to\operatorname{Aut}(G_A)$....

Let $A,B$ be irreducible integer matrices of the same spectral radius. Suppose $\operatorname{tr}(A^n)>0$ implies $\operatorname{tr}(B^n)>0$ for every...

Prove that two mixing Markov shifts admit a magic-word isomorphism exactly when they have the same beta function, the same ratio group $\Delta$, and t...

Suppose a $\mathbb Z^2$ action $\alpha$ has $\alpha^{\boldsymbol n}$ an SFT for some $\boldsymbol n$. Can $\alpha$ have infinitely many expansive comp...

If $S$ and $T$ are mixing shifts of finite type, prove that $S^i$ and $T^j$ can commute for all sufficiently large integers $i,j$....

Determine all shift-invariant Borel probability measures and all subsystems of the symbolic system $X$ constructed in Section 14 of the source from th...

For $d>1$, if a continuous factor map sends a $\mathbb Z^d$ SFT $X$ onto a sofic shift $Y$, must $X$ contain a sofic subshift $W$ with $h(W)=h(Y)$ and...

Characterize the stable limit sets of one-dimensional cellular automata....

Let $T$ be a mixing sofic shift with a receptive fixed point. When is there a block code $f:T\to T$ and an SFT $T'\supset T$ such that $f(T')\subset T...

Let $f$ be a surjective block code from a mixing sofic shift $T$ to itself. When does there exist an SFT $T'\supset T$ such that $f(T')\subset T$?...

Does every nonabelian $\mathbb Z^d$ group shift factor algebraically onto a Bernoulli group shift?...

Is every nonabelian $\mathbb Z^d$ group shift weakly algebraically equivalent to a Bernoulli group shift?...

If a translation-invariant Markov random field $\mu$ on a shift is the unique Markov random field, even without assuming translation invariance, with ...

If a $\mathbb Z^d$ SFT has a unique measure of maximal entropy and that measure is Bernoulli, must an i.i.d. process map finitarily onto it?...

Let $S$ be a one-sided subshift and $T$ the full one-sided shift on $N$ symbols, with $h(S)<\log N$, and suppose no point of $S$ has more than $N$ pre...

Classify one-sided sofic shifts up to topological conjugacy....

Give a procedure deciding whether two canonical left-resolving irreducible covers of a one-sided irreducible SFT are related by an automorphism carryi...

Are the groups $\operatorname{Aut}(\sigma_2)$ and $\operatorname{Aut}(\sigma_3)$ isomorphic?...

For a mixing SFT $S$, let $\operatorname{Aut}_0(S)$ be the inert automorphisms and $F_0(S)$ its finite-order-generated subgroup. Prove that $\operator...

Is every minimal action of a countable amenable group on the Cantor set topologically orbit equivalent to a $\mathbb Z$ action?...

For a surjective one-dimensional cellular automaton $f$ on the full $N$-shift, let $\nu(f,S_N)$ be the limsup exponential growth rate of points that a...

With $\nu(f,S_N)$ defined as in Question 25.3, must every surjective one-dimensional cellular automaton satisfy $\nu(f,S_N)\ge\sqrt N$?...

If $\beta$ is a Salem number, prove that the periodic points of the beta-transformation $x\mapsto\beta x\pmod1$ are exactly $\mathbb Q\cap[0,1)$....

Which pairs of abelian groups occur as $K_0(M,I)$ and $K_1(M,I)$ for a canonical matrix system of a subshift?...

Is every strongly mixing measure-preserving transformation strongly mixing of order three?...

Starting from a positive integer $a_0$, define $a_{n+1}=\lfloor a_n^{1/2}\rfloor$ when $a_n$ is even and $a_{n+1}=\lfloor a_n^{3/2}\rfloor$ when $a_n$...

Is the Mandelbrot set locally connected? Equivalently, for the quadratic family $z\mapsto z^2+\lambda$, is the boundary of the unbounded component of ...

For $f_\lambda(z)=\lambda z^2+z^3$, let $U$ be the parameter component where both finite critical points lie in the immediate basin of zero. Prove tha...

For $f_\lambda(z)=\lambda z^2+z^3$, let $U$ be the parameter component where both finite critical points lie in the immediate basin of zero. Prove tha...

Produce a reliable computer picture of the Julia set of a Cremer polynomial....

Are Lattès maps the only rational maps having measurable invariant line fields on their Julia sets?...

For $P_c(z)=z^2+c$ with connected Julia set, characterize the parameters $c$ for which $J(P_c)$ is locally connected....

For every degree $d$, prove that expanding (hyperbolic, Axiom A) maps are dense in the spaces $\operatorname{Rat}_d$ of rational maps and $\operatorna...

Is there a deterministic, linear-time polygon triangulation algorithm significantly simpler than that of Chazelle?...

Can the number of simple polygonalizations of a set of $n$ points in the plane be computed in polynomial time? A simple polygonalization is a simple p...

Given a visibility graph $G$ and a Hamiltonian circuit $C$, determine in polynomial time whether there is a simple polygon whose vertex visibility gra...

Given two sets of numbers, each of size $n$, how quickly can the set of all pairwise sums be sorted? In symbols, given two sets $X$ and $Y$, our goal ...