Cube-cover conjecture for diagonalization games

From papers

Let nn and mm satisfy 2n1+1m<2n2^{n-1}+1\leq m<2^n, and set

d=2nm<2n1.d=2^n-m<2^{n-1}.

For a nonempty subset J[n]J\subseteq[n], a JJ-cube is the set of binary vectors obtained by fixing all coordinates outside JJ and allowing the coordinates in JJ to vary. Cube-cover conjecture. For any collection J1,J2,,JqJ_1,J_2,\ldots,J_q of nonempty subsets of [n][n] satisfying

i=1qJi=d,\sum_{i=1}^q |J_i|=d,

there are cubes C1,,CqC_1,\ldots,C_q such that CiC_i is a JiJ_i-cube and

i=1qCid+q.\left|\bigcup_{i=1}^{q} C_i\right|\geq d+q.

This condition is equivalent to Kronecker having a winning strategy when Cantor uses mn(2nm)mn-(2^n-m) queries. The statement concerns covering the Boolean cube under prescribed coordinate freedoms and would establish optimality of the proposed strategy; its resolution is not given in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran and Shlomo Moran, “Diagonalization Games”, arXiv:2301.01924 (2023).

Solutions 0

No solutions have been posted yet.