12
$\begingroup$

For a finite $S \subset \mathbb{Z}^d$, let $d_p(S)$ be its optimal packing density. That is, the maximal lower asymptotic density of $A+S$, where $A \subset \mathbb{Z}^d$ is such that $(a_1+S)\cap (a_2+S)=\varnothing$ for all distinct $a_1,a_2 \in A$.

Does there exist a finite $S \subset \mathbb{Z}^d$ such that $d_p(S)$ is irrational?

Note that $d_p(S)=1$ if and only if $S$ tiles $\mathbb{Z}^d$. (Indeed, if $S$ does not tile $\mathbb{Z}^d$, then it does not tile some cube $[N]^d$ by compactness argument. So for every packing, at least one point in every translate of $[N]^d$ is uncovered, and thus $d_p(S) \le 1-N^{-d}$.) In the light of the latest preprint of Greenfeld and Tao, it seems that for $d \ge 3$, this function is not computable.

At the same time, if $d=1$, then the optimal packing is always periodic, with the period length bounded by $2^{\mbox{diam}(S)}$. Hence, $d_p(S)$ is computable, and the answer to my question is No in this case.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Are you sure that it follows from their preprint that the function is uncomputable for $d\ge 3$? Also, if instead of a since $S$, you allow multiple tiles that can be used, then do you have a construction? $\endgroup$
    – domotorp
    Commented Sep 23, 2023 at 21:04
  • $\begingroup$ @domotorp you are right, I don't see how uncomputablity follows from their preprint, since in Corollary 1.5 they get $d$ and a periodic $E \subset \mathbb{Z}^d$ (that can be distinct from $\mathbb{Z}^d$) as part of the input. So the computability of $d_p(\cdot)$ could be open for each $d\ge2$, but I'm not sure... $\endgroup$
    – Arsenii Sagdeev
    Commented Sep 26, 2023 at 11:53
  • $\begingroup$ @domotorp No, I do not have a constuction with several tiles where $d_p$ is irrational either $\endgroup$
    – Arsenii Sagdeev
    Commented Sep 26, 2023 at 11:55
  • $\begingroup$ And of course "since" was supposed to be "single", but I see that luckily you were more intelligent than me and you've managed to understand my question... $\endgroup$
    – domotorp
    Commented Sep 27, 2023 at 11:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .