Hadwiger covering / illumination number in ℝ^3

Description of constant

$C_{39}=H_3$ is the Hadwiger covering number in dimension $3$, which can also be formulated in terms of illumination of the boundary. <a href="#ABP2024-equivalence-illumination">[ABP2024-equivalence-illumination]</a>

Given sets $K,L\subset {\mathbb{R}}^n$, let $C(K,L)$ be the minimal number of translates of $L$ needed to cover $K$. <a href="#ABP2024-def-CKL">[ABP2024-def-CKL]</a>

For a convex body $K\subset {\mathbb{R}}^n$, write $\mathrm{int}(K)$ for its interior. The Hadwiger covering number in dimension $n$ is the minimal number $H_n$ such that any $n$-dimensional convex body can be covered by $H_n$ translates of its interior. <a href="#ABP2024-def-Hn">[ABP2024-def-Hn]</a>

The constant of interest here is $H_3$. <a href="#ABP2024-def-Hn">[ABP2024-def-Hn]</a>

For symmetric convex bodies one also considers the symmetric covering number $H_n^s$, defined analogously. <a href="#ABP2024-def-Hns">[ABP2024-def-Hns]</a>

Known upper bounds

Known lower bounds

Additional comments and links

• Conjectured exact value (open in dimension $3$). Hadwiger's covering (illumination) conjecture asserts $H_n=H_n^s=2^n$ for all $n$, hence would imply $H_3=8$. <a href="#ABP2024-conj-Hn">[ABP2024-conj-Hn]</a>

• Origin of the conjecture. Hadwiger posed the covering problem in 1957. <a href="#ABP2024-hadwiger-question">[ABP2024-hadwiger-question]</a> <a href="#Had1957">[Had1957]</a>

• Centrally symmetric case in dimension $3$. The symmetric variant is known exactly: $H_3^s=8$ (and is sharp). <a href="#ABP2024-H3s-8">[ABP2024-H3s-8]</a>

• Surveys/background for the general illumination/covering problem include <a href="#ABP2024">[ABP2024]</a>.

References

• <a id="ABP2024"></a>[ABP2024] Arman, Andrii; Bondarenko, Andriy; Prymak, Andriy. On Hadwiger’s covering problem in small dimensions. Canadian Mathematical Bulletin 68(4) (2025), 1239–1250. DOI: 10.4153/S0008439525000384. Google Scholar. arXiv PDF.
• <a id="ABP2024-equivalence-illumination"></a>[ABP2024-equivalence-illumination] loc: arXiv PDF p.1, Abstract. quote: “It is possible to define $H_n$ and $H_n^s$ in terms of illumination of the boundary of the body using external light sources,”
• <a id="ABP2024-def-CKL"></a>[ABP2024-def-CKL] loc: arXiv PDF p.1, Introduction (definitions paragraph). quote: “we denote by $C(A,B):=\min (N:\exists t_1,\dots ,t_N\in {\mathbb{E}}^n\text{ satisfying }A\subset {\bigcup }_{j=1}^N(t_j+B))$, the minimal number of translates of $B$ needed to cover $A$.”
• <a id="ABP2024-def-Hn"></a>[ABP2024-def-Hn] loc: arXiv PDF p.1, Abstract. quote: “Let $H_n$ be the minimal number such that any $n$-dimensional convex body can be covered by $H_n$ translates of interior of that body.”
• <a id="ABP2024-def-Hns"></a>[ABP2024-def-Hns] loc: arXiv PDF p.1, Abstract. quote: “Similarly $H_n^s$ is the corresponding quantity for symmetric bodies.”
• <a id="ABP2024-conj-Hn"></a>[ABP2024-conj-Hn] loc: arXiv PDF p.1, Abstract. quote: “the famous Hadwiger’s covering conjecture (illumination conjecture) states that $H_n=H_n^s=2^n$.”
• <a id="ABP2024-hadwiger-question"></a>[ABP2024-hadwiger-question] loc: arXiv PDF p.1, Introduction (paragraph after the definition of $H_n$). quote: “Hadwiger [17] raised the question of determining the value of $$\begin{gathered} H_n=\min \\ C(K,\mathrm{int}(K)):K\in K_n \end{gathered}$$ for all $n\ge 3$.”
• <a id="ABP2024-lb-cube"></a>[ABP2024-lb-cube] loc: arXiv PDF p.1, Introduction (paragraph after the definition). quote: “Considering an $n$-cube, one immediately sees that $H_n\ge 2^n$,”
• <a id="ABP2024-ub-H3-16"></a>[ABP2024-ub-H3-16] loc: arXiv PDF p.3, Introduction (paragraph on low dimensions). quote: “then to $H_3\le 16$ by Papadoperakis [24],”
• <a id="ABP2024-ub-H3-14"></a>[ABP2024-ub-H3-14] loc: arXiv PDF p.3, Introduction (paragraph on low dimensions). quote: “and then to $H_3\le 14$ by Prymak [25].”
• <a id="ABP2024-H3s-8"></a>[ABP2024-H3s-8] loc: arXiv PDF p.3, Introduction (paragraph on the symmetric case). quote: “For the symmetric case, Lassak [20] obtained the sharp result $H_3^s=8$,”

• <a id="Had1957"></a>[Had1957] Hadwiger, H. Ungelöste Probleme Nr. 20. Elemente der Mathematik 12(6) (1957), 121. Google Scholar. Publisher entry.

• <a id="Pap1999"></a>[Pap1999] Papadoperakis, Ioannis. An estimate for the problem of illumination of the boundary of a convex body in $E^3$. Geometriae Dedicata 75(3) (1999), 275–285. DOI: 10.1023/A:1005056207406. Google Scholar.

• <a id="Pry2023"></a>[Pry2023] Prymak, Andriy. A new bound for Hadwiger's covering problem in ${\mathbb{E}}^3$. SIAM Journal on Discrete Mathematics 37(1) (2023), 17–24. DOI: 10.1137/22M1490314. Google Scholar. arXiv PDF.

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 87b4ebbd426f, Apache License 2.0; reformatted for this page. New records should also be reported there.