Re: combinatorics question, should be easy

[supersede]

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 degree
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*alpha^2+b*alpha+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 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 that all other
difference set of that order can be found by applying a linear
transformation t. That is

t : S-->S', t(x)=m*x+n mod v, with m,n \in Z and m coprime to v.

Ralf
.

Relevant Pages

  • Re: combinatorics question, should be easy
    ... F_3^3 which is both a field an a three dimensional Vectorspace over ... Let alpha be a root of f. ... Powers of a root alpha of f can be seen as a basis ... if you have some difference set S it is conjectured the all other ...
    (sci.math)
  • Re: how presentation-dependent are BCH-codes?
    ... Consider alpha in G of order n, ... these are the roots of the induced Reed-Solomon code C'. ... sequence of consecutive powers of beta among the roots of g ... Alternatively a set of exponents in an arithmetic progression is allowed. ...
    (sci.math.research)
  • Re: Lets discuss big bang theory some more.
    ... alpha e^2/hbar c ... The trouble starts here in using the emasculated cgs units to evaluate ... appropriate multiplier to the initial results. ... powers of alpha, and therefore different powers of c. ...
    (sci.physics)
  • Re: Monte Cook joins Paizo for Pathfinder RPG
    ... level, Bards dramatically better in Alpha 3, the class pet replacement ... I haven't looked at Alpha 3, ... these rage-point powers are *more complicated* than the fighter ... the barbarian has never been so complex to play - can ...
    (rec.games.frp.dnd)
  • Re: Installation of SCREEN with multi access
    ... root" nor "suid alpha". ... What I did do was cd to the binaries directory and then "chmod +s ... It's supposed to be owned by user beta, but with multi set "on" so alpha ...
    (comp.unix.solaris)