How do you find a $(21,5,1)$-difference set in $(\mathbb{Z}_{21}, +)$?

Question

How do you find a $(21,5,1)$-difference set in $(\mathbb{Z}_{21}, +)$?

I already know the answer which is $\{0,1,6,8,18\}$.

But How do you get that?

Obviously, if you subtract each elements by each elements except itself, we get all the elements in $\mathbb{Z}_{21}$ (and of course.. except $0$). However, I have no idea yet of how one could get the elements in the difference set to start with.

I know this field - Combinatorial design theory is not as widely known as some other fields in math, but I'm hoping someone out there can still help.

Answer 1

This is an example of what is known as a Singer difference set. Letting $q$ be a prime power and let $m$ be a natural number, there is a general algebraic construction for difference sets with parameters $\left(\frac{q^m-1}{q-1},\frac{q^{m-1}-1}{q-1},\frac{q^{m-2}-1}{q-1}\right)$ in the cyclic group of order $\frac{q^m-1}{q-1}$; notice that this is exactly what you are asking for in the case $q=4$ and $m=3$.

So how does this construction work? Following Coulbourn and Dinitz's Handbook of Combinatorial Designs, let $\alpha$ be a generator for the multiplicative group of the finite field $\mathbb{F}_{q^m}$ and let $Tr: \mathbb{F}_{q^m} \rightarrow \mathbb{F}_q$ be the function defined by $Tr(x) = x+x^q+\cdots+x^{q^{m-1}}$. Then, setting $v = \frac{q^m-1}{q-1}$ for the sake of simplicity, the set $\{i \in \mathbb{Z}_v \,:\, Tr(\alpha^i) = 0\}$ is a $\left(\frac{q^m-1}{q-1},\frac{q^{m-1}-1}{q-1},\frac{q^{m-2}-1}{q-1}\right)$ difference set (proving this fact is a relatively straightforward exercise in undergraduate abstract algebra).

It is worth noting that the construction may not give you exactly the set you describe. For example, when I ran the general construction through sage I got the set $\{7,9,14,15,18\}$. However, the property of being a $(v,k,\lambda)$ difference set is invariant under both group automorphisms and right-regular action. Indeed, we obtain your set by subtracting each element of my set from 15.

Answer 2

Here is a simple PARI/GP program to calculate singer type difference sets [notice my handle :-)]. It doesn't use the trace since that is unnecessarily complicated. The trick is if you have the prime power order $q$ construct $\mathbb{F}_{q}^{3}=\mathbb{F}_{q^3}$ and think of it both as a three-dimensional vector space over $\mathbb{F}_{q}$ (the left side of the equation) and as the finite field with $q^3$ elements. In the latter find a primitive element x (actually any element of order $\geq q^2+q+1$ suffices but let's make it a primitive one) and look at the sequence $(x^0,x^1,x^3,\ldots x^{q^2+q})$. These elements are also elements of the vector space. Take any two dimensional subspace of it and check whether the element $x^i$ is also an element of the subspace. I chose the subspace $ax^2+bx+c$ with $a=0$. If it is then $i$ is a member of your difference set.

diffset=m-> {
  if (type(m)!="t_INT" || m<2 ,error(concat(m," is not an integer≥2")));
  if (omega(m)>1,error(concat(m," is not a prime power")));
  my(fc=factorint(m));
  my(p=fc[1,1]);
  my(n=fc[1,2]);
  my(ff=(ffinit(p,3*n))); \\ Generator for field F_{p^{3n}}
  my(lambda=ffprimroot(ffgen(ff))); \\ Generator for field F_{p^{3n}}
  my(v=p^(2*n)+p^n+1);
  my(lambda_sf=lambda^v); \\ Generator for subfield F_{p^n}
  my(s=Set([]));
  my(elem=lambda);
  for(i=0,fforder(lambda_sf),
    for(j=0,fforder(lambda_sf),
      if (i+j==0,next); 
      elem=if(i==0,0,(lambda_sf^i)*lambda)+if(j==0,0,lambda_sf^j);
      \\elem=(lambda_sf^i)*lambda+lambda_sf^j;
      s=setunion(s,Set([fflog(elem,lambda)]%v));
      if(length(s)==m+1,break(2));
    )
  );
  return(s);
}
? diffset(4)
%6 = [0, 1, 6, 8, 18] \\possibly another answer: %7 = [0, 1, 4, 14, 16]