1
$\begingroup$

Problem: Let $a_1\dots a_k$ be integers in $Z_{n}$ such that $n=k(k-1)+1$ and that the list of differences $a_i-a_j \bmod n$ is unique to $i,j$ (for $i\neq j$). Such a set exists for $k=1\dots6,8$. No such set exists for $k=7$? (Verified by exhaustive search, but I can't figure out why that case would be different. Is it possible there's an error in my code?)

Does anyone have a quick idea or a short proof of why $k=7, n=43$ would be different? Alternatively, some larger-context work that subsumes this problem and will let me figure out why $n=7$ doesn't work?

Some properties of the $a_i$: The order doesn't matter, so you might as well list them in increasing order. The set of differences has to equal every number between 1 and $n-1$ exactly once, so there will be an equivalent of any valid set that has a $0$ and a $1$. The set of differences is equivalent under rotation of the $a_i$ by addition $\bmod n$ (by design), so pick the one that starts $0,1$ as the class representative. The $a_i$ can also be represented by the $b_i$ where $b_i=a_{i+1}-a_i$. In this case the $b_i$ form a partition of $n$ with all partial sums of sequences in order of the $b_i$ being unique. The $b_i$ are equivalent under rotation of order or flipping the order, but not in otherwise reordering. (IE, the difference list $[1,2,3,4]$ is equivalent to $[1,4,3,2]$ but not $[1,4,2,3]$.)

Background: I was doing an analysis of a card game involving restricted pairs, and found some interesting properties for sets of $n=k(k-1)+1$ symbols, taken $k$ at a time, where each two sets of $k$ symbols have exactly one pair in common.

One thing I found was that I could create a maximal set using a partition slicing strategy. But I wanted to create a pattern $(a_1 \dots a_k)$ that I could simply increment around the modulus $n$ to create every possible $k-$set. What I found was that for $k=1\dots 8, k\neq 7$, I could have at least two such patterns (removing multiples via various equivalencies). However, I have been unable to find one for $k=7$, even with an exhaustive code-based search of the $[43]^7$ vector space.

$\endgroup$
  • $\begingroup$ The $a_i$ allow a "tiling" of the space by incrementing $\bmod n$. That is, if I take the $n$ additive translations of the list of $a_i$, I get $n$ $k-$element lists where each pair of translations has exactly one element in common. $\endgroup$ – JKreft Aug 3 '18 at 5:48
  • 1
    $\begingroup$ Are perfect difference sets what you are after? $\endgroup$ – Seva Aug 3 '18 at 7:40
  • $\begingroup$ YES! I'd never heard of them before. I have the necessary condition (in a different form) that n=j^2+j+1. Ah, I see that it's not a prime power (since k=7, j= 6), which all my other j's are. $\endgroup$ – JKreft Aug 3 '18 at 8:41
1
$\begingroup$

Ok, thanks to @Seva giving me the right name for these, I found out that:

  • The sets I'm describing are Perfect Difference sets.
  • The one-dimensional version I'm working with are equivalent to projective planes.
  • https://en.wikipedia.org/wiki/Projective_plane says that there is no plane for $j=6$ $(j^2+j+1)$, which is equivalent to my case where $k=7$ $(k^2-k+1)$.

So, not an error in my code, proven impossible prior to 1938 (as a different problem) and related to projective planes in 1938.

$\endgroup$
  • 1
    $\begingroup$ more precisely, a finite projective plane with an automorphism that acts on the points by cyclic permutation. Since there's no projective plane of order 6, a fortiori there is none with a 43-cycle automorphism. $\endgroup$ – Noam D. Elkies Aug 3 '18 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.