TheoremDB

Erdős Problem 51: Let $\varphi$ denote Euler's totient function, which counts the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. For a positive integer $a$, let $\varphi^{-1}(\{a\})$ denote the set…

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…

For a finite binary word \(w\) and \(x\in\{0,1\}\), let \(r_w(x)\) be the largest integer \(r\ge 1\) for which \(wx\) ends in \(u^r\) for some nonempty word \(u\), and let \(\ell_w(x)\) be the largest length \(|u|\)…

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

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?

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

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…

Erdős Problem 52: Let $A$ be a finite set of integers. For every real number $\varepsilon$ with $0 < \varepsilon < 1$, does there exist a real constant $C > 0$ such that \[ \max(|A+A|, |A \cdot A|) \geq C \cdot…

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…

Does there exist an infinite-dimensional real or complex Banach space \(X\) such that every bounded linear operator \(T:X\to X\) attains its operator norm?

Determine the exact capacity region of the memoryless real two-user Gaussian interference channel \(Y_1=X_1+aX_2+Z_1\) and \(Y_2=bX_1+X_2+Z_2\) for arbitrary fixed \(a,b\in\mathbb R\), independent standard Gaussian…

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?

Erdős Problem 51: Let $\varphi$ denote Euler's totient function, which counts the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. For a positive integer $a$, let $\varphi^{-1}(\{a\})$ denote the set…

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…

For a finite binary word \(w\) and \(x\in\{0,1\}\), let \(r_w(x)\) be the largest integer \(r\ge 1\) for which \(wx\) ends in \(u^r\) for some nonempty word \(u\), and let \(\ell_w(x)\) be the largest length \(|u|\)…

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

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?

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

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…

Erdős Problem 52: Let $A$ be a finite set of integers. For every real number $\varepsilon$ with $0 < \varepsilon < 1$, does there exist a real constant $C > 0$ such that \[ \max(|A+A|, |A \cdot A|) \geq C \cdot…

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…

Does there exist an infinite-dimensional real or complex Banach space \(X\) such that every bounded linear operator \(T:X\to X\) attains its operator norm?

Determine the exact capacity region of the memoryless real two-user Gaussian interference channel \(Y_1=X_1+aX_2+Z_1\) and \(Y_2=bX_1+X_2+Z_2\) for arbitrary fixed \(a,b\in\mathbb R\), independent standard Gaussian…

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?