4

Let $n=8m+1, m\in\mathbb{N}$. Does the set of nonzero elements of $\mathbb{Z}_n$ split into disjoint octets of the form $8_k=\{\pm a_k,\pm b_k,\pm a_k\pm b_k\}$?

The computer tells me it is possible if $n$ is not a multiple of 3, up to $n=113$. Larger $n$ have many solutions; $n=73$ has thousands of solutions.

For example, $Z_{17}\backslash\{0\}=\{\pm 1,\pm 4,\pm 1\pm 4\}\cup\{\pm 2,\pm 8,\pm 2\pm 8\}=\{\pm1,\pm4,\pm3.\pm5\}\cup\{\pm2,\pm8,\pm10,\pm6\}$

My motive is this: I am idly wondering whether there are $m$ patterns like this:

  • Each pattern has an $n$-omino. This $n$-omino has $n$ different coloured tiles, and it tiles the plane by translations.
  • Different patterns may have different $n$-ominoes, but the same $n$ colours.
  • Any two colours are adjacent (edge or corner) in exactly one pattern.
  • A solution would be to colour tile at $(c,d)$ in pattern $k$ with colour $ca_k+db_k(\bmod n)$.
Empy2
  • 50,853
  • The natural condition would be that $8 | \varphi(n)$, right? – Qiaochu Yuan Jul 17 '14 at 05:40
  • Ah. Why is that? – Empy2 Jul 17 '14 at 06:04
  • 1
    Oh, sorry, nonzero elements. The condition in the title is not the condition in the body; $\mathbb{Z}_n^{\times}$ is strictly smaller than the nonzero elements unless $n$ is prime. – Qiaochu Yuan Jul 17 '14 at 06:05
  • I don't get it. $3$ is in ${\bf Z}_{17}^{\times}$, right? But $3\ne\pm1$, $3\ne\pm4$, $3\ne\pm2$, and $3\ne\pm8$. So what's going on here? – Gerry Myerson Jul 17 '14 at 06:19
  • Sorry Qiaochu, the title is fixed now. – Empy2 Jul 17 '14 at 07:29
  • @GerryMyerson, 3=-1+4 – Empy2 Jul 17 '14 at 07:29
  • That is, the first set contains $\pm 1,\pm 4,\pm3$ and $\pm5$. The second set contains $\pm 2,\pm 8,\pm 10(=\pm 7)$ and $\pm6$. – Empy2 Jul 17 '14 at 08:09
  • Ah, I missed that there's no comma before the last $\pm$. – Gerry Myerson Jul 17 '14 at 09:17
  • If $n$ is a multiple of 3, then each octet contains either 2 or 8 multiples of 3. It turns out that $n$ must be $72k+9$ in this case. There are solutions for $n=81$, but they don't work for my patterns because all the colours would be multiples of 3. – Empy2 Jul 21 '14 at 04:03
  • Suppose I replace $a_k\pm b_k$ with a random pair for each $a_k,b_k$. There are $(4m)!/[2^mm!(2m)!]$ sets of $(a_k,b_k)$. The chance that any one set gives a solution is $(2m)!/(4m)^{2m}$, so the average number of solutions is $(4m)!/[m!32^mm^{2m}]$, which grows quickly with $m$. In other words, I would expect lots of solutions, with no other particular reason. – Empy2 Jul 27 '14 at 07:08

0 Answers0