Skip to main content
2 of 3
added 2 characters in body
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

Take any maximal face $a$ in the pre-image of $(*,*,*)$ (i.e., of the 3-dimensional face). W.l.o.g., it has the form $a=(\underbrace{*,\dots,*}_k,0,0,\dots,0)$. Denote by $a(p,q)$ the face obtained from $a$ by replacing the $p$th star with $q$ (so $1\leq p\leq k$ and $q\in\{0,1\}$).

We say that a bit is determined if it is not a star. Notice that each $f(a(p,q))$ has a determined bit.

1. Assume that $f(a(p,0))$ and $f(a(p,1))$ have some determined bits in different positions, say $f(a(p,0))$ has the first bit $0$, and $f(a(p,1))$ has the second bit $0$. Then there is no $y\geq a$ such that $f(y)=(1,1,*)$. Indeed, if $y$ has a determined first bit, then $f(y)$ has $0$ in the corresponding bit. Otherwise, if $y$ has a star in the first bit, then replace it by $0$ to get $y_0$. We have $f(y_0)=(0,\dots)$, so we cannot have $f(y)=(1,\dots)$.

Thus, each of $f(a(p,0))$ and $f(a(p,1))$ has a unique determined bit, and those bits are at the same position $s(p)\in\{1,2,3\}$.

2. Assume that $f(a(p,0))$ and $f(a(p,1))$ coincide, say $f(a(1,0))=f(a(1,1))=(0,*,*)$. Then there is no $y\geq a$ with $f(y)=(1,*,*)$. The reasoning is similar: if the first bit of $y$ is determined, then that of $f(y)$ is $0$; otherwise, replace the first bit in $y$ by $0$.

Thus, $f(a(p,0))$ and $f(a(p,1))$ differ in exactly $s(p)$th bit, the others being stars.

3. Assume that the function $s$ is not injective, say $s(1)=s(2)=1$. We may assume that $f(a(1,0))=(0,*,*)$ and $f(a(2,1))=(1,*,*)$. Then there is no image for $(0,1,\underbrace{*,\dots,*}_{k-2},0,\dots,0)$.

Thus $s$ is injective, which yields $k\leq 3$.

Ilya Bogdanov
  • 23.7k
  • 54
  • 92