GeMeCoD open problems

This page gathers some open mathematical problems related to the GeMeCoD project.

The Fourier-Entropy-Influence conjecture

Let $\mu$ be the uniform probability measure on the discrete cube $\{-1,1\}^n$, i.e. $\mu(A)=2^{-n}\mathrm{Card}(A)$ for every $A\subset\{-1,1\}^n$. Let us consider a Boolean function $$f:\{-1,1\}^n\to\{-1,1\}.$$ For every $1\leq i\leq n$, the influence of the $i$-th coordinate on $f$ is $$I_i(f)=\mu(A_i(f))$$ with $A_i(f)=\{x\in\{-1,1\}^n:f(x)\neq f(\tau_i(x))\}$ where $\tau_i(x)$ is obtained from $x=(x_1,\ldots,x_n)$ by flipping the $i$-th coordinate. The total influence of $f$ is $$I(f)=I_1(f)+\cdots+I_n(f)=\mu(A_1(f))+\cdots+\mu(A_n(f)).$$ One may check this definition on various simple examples such as $f(x)=x_1\cdots x_n$, $f(x)=\mathrm{sign}(x_1+\cdots+x_n)$, or $f(x)=\max(x_1,\ldots,x_n)$. Boolean functions are used in the modeling of the status of non-linear discrete systems with multiple components, such as for the percolation phenomenon, for the connectivity of random graphs, or for the invertibility of $\pm 1$ matrices (the geometrical structure of the model is captured by the specific function $f$, which is rarely fully symmetric).

The total influence of $f$ is a measure of its one dimensional complexity. Another way to measure the complexity of $f$, more global, is to consider the entropy of its Fourier transform (squared). Let us denote by $\hat f$ the Fourier transform of $f$ on $\{-1,1\}^n$. The Fourier-Entropy-Influence (FEI) conjecture formulated by Friedgut and Kalai in 1996 states that there exists a real constant $c>0$ such that for every Boolean function $f:\{-1,1\}^n\to\{-1,1\}$, $$\mathrm{Ent}(\hat f^2)\leq cI(f).$$ If $\partial_if=(f-f(\tau_i))/2$ stands for the discrete gradient acting on the $i$-th coordinate then $\partial_if$ takes its values in $\{-1,0,1\}$ and $$A_i(f)=\{x\in\{-1,1\}^n:(\partial_i f)(x)\neq0\}=\{x\in\{-1,1\}^n:(\partial_i f)^2(x)=1\}$$ and thus $$I(f)=\mu\left(\sum_{i=1}^n(\partial_i f)^2\right).$$ However, beware of the apparent similarity with the Gross logarithmic Sobolev inequality (which formulates hypercontractivity).

The Kesten-McKay conjecture

Random oriented graphs are host of many open problems. For example, for integers $n \geq r \geq 3$, an oriented $r$-regular graph is a graph on $n$ vertices such that all vertices have $r$ incoming and $r$ outgoing oriented edges. Consider the adjacency matrix $A$ of a random oriented $r$-regular graph sampled from the uniform measure (there exists suitable simulation algorithms using matchings of half edges). Let $\mu_A=\frac{1}{n}\sum_{k=1}^n\delta_{\lambda_k}$ be the counting measure of the eigenvalues of $A$ (roots of the characteristic polynomial in $\mathbb{C}$). It is conjectured that as $n \to \infty$, almost surely $\mu_A$ converges to the probability measure \[ \frac{1}{\pi} \frac{r ^2(r-1)}{(r^2 - |z|^2)^2 }\mathbb{1}_{\{|z|<\sqrt r\}}\,dxdy. \] It turns out that this probability measure is also the Brown measure of the free sum of $r$ unitary, see Haagerup and Larsen. The Hermitian (actually symmetric) version of this measure is known as the Kesten-McKay distribution for random non-oriented $r$-regular graphs, see Kesten and McKay. We recover the circular law when $r\to\infty$ up to renormalization.

This paragraph was extracted from Around the Circular Law, by Bordenave and Chafaï (2011)

Invertibility of random matrices

Let $M=(M_{ij})_{1\leq i,j\leq n}$ be a $n\times n$ matrix with symmetric Bernoulli $\pm 1$ entries. A convenient way to quantify the invertibility of $M$ is to consider the smallest singular value $$ s_n(M):=\min_{\left\Vert x\right\Vert_2=1}\left\Vert Mx\right\Vert_2. $$ Indeed, if $M$ is invertible then $s_n(M)=\Vert M^{-1}\Vert_{2\to2}^{-1}$. Note also that $\det(M)=0$ if and only if $s_n(M)=0$. A famous conjecture by Spielman and Teng related to their work on the smoothed analysis of algorithms states that there exists a constant $0<c<1$ such that \[ \mathbb{P}\left(s_n(M)\leq t\right)\leq t+c^n \] for $n\gg1$ and any small enough $t\geq0$. This was almost solved by Rudelson and Vershynin and by Tao and Vu. In particular, taking $t=0$ gives \[ \mathbb{P}(M\text{ is singular})=c^n. \] This positive probability of being singular does not contradict the asymptotic invertibility since by the first Borel-Cantelli lemma, a.s. $M$ is not singular for $n\gg1$. Regarding the constant $c$ above, it has been conjectured years ago that \[ \mathbb{P}(M\text{ is singular})=\left(\frac{1}{2}+o(1)\right)^n. \] This intuition comes from the probability of equality of two rows, which implies that $\mathbb{P}(M\text{ is singular})\geq(1/2)^n$. Many authors contributed to the analysis of this difficult nonlinear discrete problem, starting from Komlos, Kahn, and Szemerédi. The best result to date is due to Bourgain, Vu, and Wood who proved that \[ \mathbb{P}(M\text{ is singular})\leq \left(1/\sqrt{2}+o(1)\right)^n. \]

The Mahler conjecture

If $K$ is a convex body in $\mathbb{R}^n$ and $z$ is an interior point of $K$ the polar body $K^z$ of $K$ with center of polarity $z$ is defined by $K^z = \{y\in\mathbb{R}^n : \langle y-z,x-z\rangle\le 1 \mbox{ for all } x\in K\}.$ The bipolar theorem says that $(K^z)^z =K$. The volume product of $K$ is defined by $$\mathcal{P}(K) = \inf \{|K| |K^z| : z\in {\rm int}(K)\}.$$ The volume product is affinely invariant, that is $\mathcal{P}(A(K))=\mathcal{P}(K)$ for every affine isomorphism $A$. The Blaschke-Santaló inequality (proved by Blaschke in dimension 2 and 3 and Santaló in higher dimension) states that $$ \mathcal{P}(K) \le \mathcal{P}(B^n_2), $$ where $B^n_2$ is the Euclidean ball (or any ellipsoid), with equality only for ellipsoids. Simple proofs were given by Meyer-Pajor and Meyer-Reisner.

The minimal value of $\mathcal{P}(K)$ is still unknown. Mahler's conjecture states that, for every convex body $K$ in $\mathbb{R}^n$, $$\mathcal{P}(K) \ge \mathcal{P}(\Delta^n)=\frac{(n+1)^{n+1}}{(n!)^2}$$ where $\Delta^n$ is an $n$-dimensional simplex with equality only if $K$ is a simplex. The symmetric case of Mahler conjecture states that for every convex symmetric body $K$: $$\mathcal{P}(K) \ge \mathcal{P}([-1,1]^n)=\frac{4^{n}}{n!}.$$ These inequalities for $n=2$ were proved by Mahler. Saint Raymond established the case of unconditional bodies (bodies symmetric with respect to the coordinate hyperplanes) Meyer and Reisner together and separately treated other cases, like e.g. bodies of revolution, or $n$ dimensional polytopes with at most $n+3$ vertices or zonoids. Barthe and Fradelizi proved stronger inequalities for convex bodies having hyperplane symmetries which fix only one common point. Nazarov, Petrov, Ryabogin and Zvavitch proved the conjecture for bodies close to the cube; Kim and Reisner for bodies close to the simplex.

Even in dimension 3, it is still open.

Observe that the (non-exact) reverse Santaló inequality of Bourgain and Milman is $$\mathcal{P}(K) \ge c^n\mathcal{P}(B^n_2)$$ where $c$ is a positive constant; Kuperberg gave a new proof of this result with a better constant and Nazarov found an harmonic analysis approach to the inequality.

Functional forms of the conjectures were also formulated and proved in some particular cases (dimension $1$ and the case of unconditionnal functions for example) by Fradelizi and Meyer. One of these conjectures asserts that for any even convex function $\varphi$, $$\int e^{-\varphi}\int e^{-\mathcal{L}\varphi}\ge 4^n,$$ with equality for $\varphi(x)=\|x\|_{\infty}$, where $\mathcal{L}\varphi(y):=\sup_x\langle x,y\rangle -\varphi(x)$ denotes the Legendre transform of $\varphi$. The non-symmetric variant form of the conjecture asserts that $$\inf_{z\in\mathbb{R}^n}\int e^{-\varphi}\int e^{-\mathcal{L^z}\varphi}\ge e^n,$$ with equality for $\varphi(x)=\sum_{i=1}^nx_i{\bf 1}_{\mathbb{R}_+^n}$, where $\mathcal{L^z}\varphi(y):=\sup_x\langle x-z,y-z\rangle -\varphi(x)$.

Yet another conjecture


openproblems.txt · Last modified: 2012/11/26 23:33 (external edit)
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki