Re: combinatorics question, should be easy

Jeremy Targett wrote:

Ralf Goertz <r_goertz@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

I'm not sure I understand everything you said, but I used to deal
with those sets and I wrote a program that generates them for the
case y=1, v=q^2+q+1 and k=q+1. One difference set for your example
would be {0, 1, 4, 6}. This I construct by taking F_3, extending it
using the irreducible and primitive polynomial f=X^3+2*X^2+X+1 to
F_3^3 which is both a field an a three dimensional Vectorspace over
F_3. Let alpha be a root of f. Then the elements of the difference
set are those exponents i modulo 13 for which alpha^(i+1) is in the



plane <alpha^2,alpha>.

Thanks Ralph - I'm afraid my lack of training means I can't follow
your method, though it seems very clearly stated. My problem is that I
thought the CRC handbook's description was straight-forward enough
that I understood it all--but when I carry it out, it just doesn't
work! Could there be a mistake? It's much more likely I'm doing
something wrong.

I'd like to try again, since I very much loved those sets. The biggest I
ever created was one with the order (=q=k-1) 45763. Having read your OP
again I assume that your problem seems to be the generator of
F_(q^(d+1)), although I do not fully understand why the CRC recipe wants
you to /sum/ anything. In the example you gave q^(d+1)=27 but you seem
to have tried to use F_13. But 13 is just v=3^2+3+1 the module of the
difference set. The theory for the case y=1, v=q^2+q+1, k=q+1 goes like
this: q=p^n must a prime power. Then we have the finite Field F_q. This
can be extended to F_q^3 by using an irreducible polynomial f of order
3. Obviously, since q^3 is not prime the Field F_q^3 is not Z/q^3Z. Now
we look at F_q^3 as being a three-dimensional vector space V over F_q.
Powers of a root alpha of f can be seen as a basis
(alpha^2,alpha,1=alpha^0), that is every element of F_q^3 can be written
as a*q^2+b*q+c with a, b, c elements of F_q. Interestingly, if f is not
only irreducible but also primitive, alpha is also a generator of
F*_q^3=F_q^3\{0}, so for every field element m except 0 we have
m=alpha^i for some 0<=i<q^3. The trick now is to check wether those
powers of alpha are in some hyperplane of the *vector* *space* V. An
easy choice for this hyperplane would be <alpha^2,alpha> that is all the
elements of F_q^3 that can be written as a*alpha^2+b*alpha. Since F*_q^3
has q^3-1 elements this are (q^3-1)/(q-1)=q^2+q+1=v. In our example we
construct the difference set S as follows:

alpha^(0+1)=0*alpha^2+1*alpha+0 => 0 \in S
alpha^(1+1)=1*alpha^2+0*alpha+0 => 1 \in S

Now, since alpha is a root of f we have

alpha^3+2*alpha^2+alpha+1=0 and therefore

alpha^(2+1)=-2*alpha^2-alpha-1=1*alpha^+2*alpha+2 => 2 \not\in S
alpha^(3+1)=(alpha^3)*alpha=alpha+2 => 3 \not\in S
alpha^(4+1)=(alpha^4)*alpha=alpha^2+2*alpha => 4 \in S
alpha^(5+1)=(alpha^5)*alpha=2*alpha+2 => 5 \not\in S
alpha^(6+1)=(alpha^6)*alpha=2*alpha^2+2*alpha => 6 \in S

All other powers up to 12+1 are not in the hyperplane, we know that
because we have found all four elements of S already. We do not need to
check further. Hence we arrive at S={0,1,4,6}. And indeed

1=1-0
2=6-4
3=4-1
4=4-0
5=6-1
6=6-0
7=0-6
8=1-6
9=0-4
10=1-4
11=4-6
12=0-1

modulo 13.

Details can be found in Singers article "A theorem in finite projective
geometry and some applications to number theory", Transactions of the
American Mathematical Society, 43(3):377â??385, 1938.

Now, if you have some difference set S it is conjectured the all other
difference set of that order can be found by applying linear
transformations t. That is

t : S-->S', t(x)=m*x+n mod v, where m must be coprime to v.

Ralf
.

Relevant Pages

  • Re: combinatorics question, should be easy
    ... Let alpha be a root of f. ... Powers of a root alpha of f can be seen as a basis (alpha^2, alpha, ... if you have some difference set S it is conjectured that all other ...
    (sci.math)
  • Re: combinatorics question, should be easy
    ... member of the field since alpha is a generator) such that beta + ... So the difference set would be S'=which turns out to be a ... *nonprime* finite Field alpha will never be an element of Z. Therefore ...
    (sci.math)
  • Re: combinatorics question, should be easy
    ... the difference set S as follows: ... I think I see the nature of your test - for every power alpha^n ... the powers of alpha, which means I can't write a little program to do it. ... Let alpha be a generator of the multiplicative group of F_). ...
    (sci.math)