2-Designs and a differential equation

0047-2468/84/020178-0551~50+0.20/0

Journal of G e o m e t r y Voi.22 (1984)

2-DESIGNS

Johannes

9 1984 B i r k h ~ u s e r Verlag~

AND A DIFFERENTIAL

Basel

EQUATION

Siemens

We show that 2-designs with given parameters v~k~J~ are in one-to-one c o r r e s p o n d e n c e to polynomials that solve a certain differential equation and have coefficients equal to zero or one~ From this result we derive an existence theorem w h e r e b y designs correspond to integer points on a sphere in E u c l i d e a n Space.

Let

D

be a design on the point

with parameters termined

2-(v,k,%)

variables

for some field

in the polynomial

R

For a block Pb =

and we represent

the design

where the sum expands shall show that More important

PD

set

X = (x10x 2 .... ~x v}

.We shall regard these points b

H xi~b D

ring in

as in

the monomial I)

by the polynomial

of

D .In this note we

a certain differential

is the fact that the solutions

that are polynomials

= R[Xl,X 2 ..... Xv]

we define

x. m

over all blocks satisfies

R[X]

D

as unde-

(2) represent

equation.

of this equation

all designs

on

X

these parameters. On

R[X] we define =

the d i f f e r e n t i a l

~/~x I

+ ~/~x 2

operator

+ .,. + ~/~x v

(3)

with

Siemons

179

When its powers

8

i

are applied

~i(P b) : i! 9 [ where

the sum expands

b .For

i h k

xjl-xj2

over all

the right hand

i = k ) and as 0 inner product by

and

Q

Using

equation

9

in the remaining

are monomials (4)

obtain

P # Q P = Q

~2

PD

be the symmetric

(7)

xi.x j

is independent

satisfies

R[X]m

denote

by monomials

2-(v,k,~) P

an

I

xi,x. in b J

(6)

xi,x j

we

with

of degree

i ~ j

2 , i.e.

The value

of the particular

(k-2)!

the linear m

of

pair

1

~2

is

in equa-

xi,x j .Therefore

9 ~ 9 ~2 " solutions

subspace

variables

of

0

is a or

where

that

(0,1)-polynomial and

1

the

"block"

(8) one concludes

of this equation. that is spanned

in the first power P

in

P = PD

R[X]k,

for some design

D

has parameters

are the values

in equation

Xl.X 2.

( with

...-x k,

b = {Xl,X2,...,Xk,} easily that

solves

, i.e. all its coefficients

I .We shall also show that k

(8)

R[X]

appearing

.We shall demonstrate P

we define and

(7)

9

polynomial

For each monomial (4)

equal to

the pair

that for some k" a polynomial

(8)

provided

are either

in

containing

we now consider

in any

.Suppose

equation D

we define

the equation

Conversely

only

(if

(5)

if the pair is contained otherwise

(k-2)!

~k-2(P D) =

Let

i!

that

blocks

, x l..xJ.> =

the sum over all tion

R[X]

as

the equation < 8k-2(PD)

Let

1

of the block

is defined

.In

if

, xi'x~j >=

are exactly

subsets

(4)

if

0 As there

obtain

(~)

with coefficient

we observe

in (1)we

.X.jk_i

case

i (k-2)[ < 8k-2(P b)

.

9

side of

{~ P

o

(k-i)-element

< P ' Q >= when

to the monomials

(8)

coefficient

I )

. From equation

k = k" so that every

180

$iemons

block contains

exactly

x i 9x.J

product

b 2 ..... bs

k

appears

points

p r e c i s e l y in

be all blocks

Ps

be the corresponding

(6)

,we obtain

.We now have to show ~~ha~ ~ any

containing

and also as a consequence

, xi'x"

J

'

i = s

tic of

is zero or at least

= X

I:

for every pair

equation

' P2 '''

according

k-1

to

(9)

(8) >= < ~k-2(p)

xi,x j

The class of all designs

~k-2(p)

P1

bI

, x. ox~ > = i

~ 9 (k-2)! provided

J

(10)

the characteris-

.Under the latter

condition

on the point

(x !,~

the proof of

with parameters

to the class of

P .Let

and let

P .Then,

02 , xi.x j >=

Therefore

THEOREM

of

, xi.x. >= J

< ~k-2(P1+P2+o " +pz)

R

in

of equation

9 (k-2)!-<

blocks

xi.x j

polynomials

< ~k-2(PI+P2+~..+Ps

we have completed

l

2-(v,k,~)

(0,1)-polynomials =

in

R[X] k

~

correspondence

that solve the

l" ( k - 2 ) ! " a 2

Note that the solution mials is equivalent

set

is in one-to-one

of equation

to the quadratic ~k-2(p) 0

=

~. (k_2)! . a 2

<

P

<

(8) for

programming

(0,1)-polyno~

probl~m

1

max < P ~ P >

(11)

Here we use the customary

convention w h e r e b y

that all coefficients

P

of

We now restrict

a ! P ! b

belong to the interval

ourselves

to the case where

means

[a,b] R

is the

rational field and k ~ v-2 .In [3] ! have shown that the operator 8k-2: R[X] k ---> R[X]2 is surjeetive .So if K denotes 8k-2 the kernel of K has dimension (~) - (~) and a set of vectors

spanning

K

can be c o n s t r u c t e d

from the formula

in lemma

Siemons

181

2.3 in [3] equation geneous

(8) where degree

ak

Z+

the general

be the cone in

S ~ 0 .Finally let B(gk,r)

now is the symmetric

k .Therefore

Z = a k + K .Let

and

v-2)-1"l'a k gk = (k-2

.It is easy to see that

S(ak,r)

Z

polynomial

solution whose

of

, < P-a~

sphere

and the open ball with centre

tively

.An integer

point in

R[X]

, P-a~> ak

of homo(8)

elements

= { P I P e R[X] k , < P-a~

= {P I P s R[X]k

solves

<

is

S

satisfy

, P-a k > = r 2}

r 2}

be

and radius

the

r

is an element whose

respec-

coordinates

all are integers. EXISTENCE

2: For given

THEOREM

given by

parameters

v,k,X v-2)-I, (k-2

r2 = l ' v ' ( v - 1 ) ' ( k ' ( k - 1 ) ) - 1 " ( 1 -

Z+~ B(ak,r)

contains

these parameters

no integer

points

if and only if

let

be

l) .Then

.There is a

Z+~ S(ak,r)

r

2-design

contains

with

integer

points. Proof: w(P)

For an element

=
similarly

ak>

P

in

R[X]k

~ the weight

.Let

u

of an element

be the operator

to the given inner product

the weight adjoint

is defined

in to

.It is easy to see

~[~]2 ~

by

is defined with respect

~for instance

from

equation (4) ,that u(g2) = I/2 . k ! . a k . Therefore w(~k-2(P))= ~k-2 < (P),a 2 > = < P , ~(a 2) > = w(P).I/2.k! .Hence elements in K have weight zero and any solution of equation (8) has weight w(P)

If

P

=

< ak

is an integer

, ak>

point

=

in

~.v(v-1)/k(k-1]

Z+

then

(12)

< P , P > > w(P)

.Hence

m

, P-a~

< P-a

v-2 -I. ~+ < P , P > - 2.< P , ak >.(k_2)

> =

v-2 i w(P).(1 - 2(k_2)-I.~) = r

2

.This

point

shows that

.Now observe

coefficients < P-a~

, P-a~

of

Z+~B(ak,r)

that

P

v-2)-2 + (k-2 " 12 "(kv) = w(P) " (I

w(P)

are either

> = r2

design with parameters

does not contain

= < P , P > 0

or

if and only if v,k,l

v-2)-I. (~-2

~)

any integer

if and only if the

I .Therefore P

< a~ , a~ >

,by theorem I,

is the polynomial

.This completes

the proof

of a

182

Siemons

We conclude with a remark on automorphism groups ~ symmetric group on transformations .As

X

acts on 8

and

~2

symmetric group also acts on elements in

R[X]k Z

as a group of linear

are permutation invariant ~the and in particular on the

Z .Therefore the orbits of

in

Z+N S(O~,r)

on

X

[0,1)-

(0,1)-elements contained

correspond to the isomorphism classes of designs

with given parameters .The automorphism group of a design

thus is the stabilizer of the corresponding integer point .So,if a design with given parameters should exist,we find a% least v!/d integer points in

p

~+~ S(Ok~r)

where

d

is the order of the au-

tomorphism group of the design.

REFERENCES [1]

F.Fricker, EinfGhrung in die Gitterpunktlehre, Birkhiuser Verlag; Basel,Boston,Stuttgart. 1982.

[2]

L.G.Ha~ijan, A polynomial algorithm in linear programming, Soviet Math. Dokl. Vol. 20, No.I, 191-19~. 1979.

[3]

J.Siemons, On 9artitions and permutation groups on unordered sets, Arch. Math. Vol. 38~ 391-403. 1982.

Department of Mathematics University College Dublin Belfield Dublin 4 Republic of Ireland

Rittnertstra3e 53 D 75oo Karlsruhe West Germany

(Eingegangen am 14. September 1983)