maths14

AN OLD QUESTION

1. A b s t r a c t

In the seventies we investigated which triples (n,e,q) of parameters for perfect e-error-correcting codes with word length n and symbols from an alphabet with q elements are possible.
This research had been initiated by van Lint (see (B)), continued by the author of this article and others (see (C)), and almost completed by Best (see (A)). The case e=2 is not yet completed.

The writer of this article has investigated (in the years from 1973 to 1977), among other things, a number of special cases with e=2 (see (C)).
Continuing in this way we can find many new partial results, but that doesn't make headway. The purpose of this article is to show that a completion of the case e=2 cannot be shortly expected.

2. I n t r o d u c t i o n

Necessary conditions for the existence of perfect (n,e,q)-codes with e=2 are:

2.1 --- 1 + n(q-1) + (n(n-1)/2)(q-1)² divides qⁿ

(the sphere packing condition), and

2.2 --- (n-x)(n-x-1)(q-1)² - 2(n-x)(x-1)(q-1) + (x-1)(x-2) has two different integral zeroes greater than 0 and smaller than n+1

(the polynomial condition).

Our research concentrates on these two conditions.
There are other conditions, for example inequalities in relation to the zeroes, and conditions regarding divisibility that follow from the existence of t-designs in perfect codes (see (B), (C)), but these conditions are not strong enough to make substantial contributions to a complete solution of the problem.

Notice that (n,q)=(11,3) satisfies the conditions (the 'Golay parameters', see (B)). Of course this holds for (2,2) as well (trivial code) and for (5,2) (repetition code). Other solutions with e=2 and n>5 have never been found. We want to prove that no other solutions exist.

3. R e - f o r m u l a t i o n (for odd q)

To consider the problem from a different point of view, we write n-x = y.
The (2.2) becomes:

(3.1) --- q² y² - (q² - 4q + 2nq)y + (n-1)(n-2) has two integral zeroes y1 en y2, and

(3.2) --- y1 + y2 = 1 + 2(n-2)/q en y1 y2 = (n-1)(n-2)/q².

We continue with odd q; this is the simplest case with regard to (3.2).
Then from (3,2) follows that a natural number k exists with

(3.3) --- n = 2 + k q².

The discriminant of (3.1) is then
(y1 - y2)² = (y1 + y2)² - 4 y1 y2 = 1 + 4k(q-1), so a natural number m exists with
1 + 4k(q-1) = (2m+1)², or (equivalently)

(3.4) --- k(q-1) = m(m+1).

Using (3.3) and (3,4), the sphere packing condition (2.1) becomes

(3.5) --- 1 + (1/2)m(m+1)(3q - 1 + m(m+1)q²) divides qⁿ

(with m=1 and q=3 we get the Golay parameters).
From (3.4) we see

(3.6) --- q is smaller than 2(m+1)².

for odd q, the conditions (3.5) and (3.6) are nearly as strong as (2.1) and (2.2). But what can we do with them?

4. C o n t i n u e d - r e s e a r c h (odd q)

We look for pairs (m,q) that satisfy (3.5) and (3.6).
If a prime p divides the left hand side of (3.5), then it follows from condition (3.5) that p divides q as well, so

(4.1) --- p divides m(m+1) - 2 (and p is not equal to 2, because q is odd).

For given m we now find in some cases that the left hand side of (3.5) must be a prime power. This follows from the following list of possible pairs (m,p):

(4.2) ---

m: 3 4 5 6 7 8 9 10 11 12 13 14

p: 5 3 7 5 3 5,7 11 3 5,13 7,11 3,5 13

For example, with m=7 we find

(4.3) --- (-3³) + (2² 3 7 q) + (2⁵ 7² q²) = 3² (q a natural number smaller than 128),

and we can check that such q doesn't exist.

Thus we see that for each fixed m the research is easy (for fixed q it is more difficult, see (C)).
On the other hand, such p vary with variing m, and often more than one p is possible (see (4.2));
and we can not generally exclude that the left hand side of (3.5) has a small amount of distinct prime factors for some value of m or some value of q smaller than 2(m+1)² .

So it remains possible that our question will become in future a very old one indeed.

5. L i t e r a t u r e

(A) MR Best : On The Existence Of Perfect Codes; Mathematisch Centrum Amsterdam 1978

(B) JH van Lint : Coding Theory; Springer Verlag Berlin etc 1973

e-mail: info@petericepudding.com (I don't open appendices)

click here to go back to my homepage

klik hier om terug te gaan naar mijn hoofdpagina

EEN OUDE KWESTIE

1. S a m e n v a t t i n g

In de jaren zeventig is onderzoek gedaan naar mogelijke parameters (n,e,q) voor perfecte e-fouten-verbeterende codes met woordlengte n en symbolen uit een alfabet met q elementen.
Dit onderzoek werd gedaan door van Lint (zie (B)), voortgezet door auteur dezes en anderen (zie (C)), en grotendeels voltooid door Best (zie (A)). Het geval e=2 is nog niet afgerond.

De schrijver van dit artikel heeft van 1973 tot 1977 onder meer een aantal speciale gevallen met e=2 onderzocht (zie (C)).
Zo voortgaande kan men veel nieuwe deelresultaten vinden, maar dat schiet niet op. Doel van dit artikel is aan te tonen dat een afronding van het geval e=2 niet spoedig verwacht mag worden.

2. I n l e i d i n g

Nodige voorwaarden voor het bestaan van perfecte (n,e,q)-codes met e=2 zijn:

2.1 --- 1 + n(q-1) + (n(n-1)/2)(q-1)² deelt qⁿ

(de bolpakkingsvoorwaarde), en

2.2 --- (n-x)(n-x-1)(q-1)² - 2(n-x)(x-1)(q-1) + (x-1)(x-2) heeft twee verschillende gehele nulpunten groter dan 0 en kleiner dan n+1

(de polynoomvoorwaarde).

Het onderzoek concentreert zich op deze twee voorwaarden.
Er zijn er nog andere, bijvoorbeeld ongelijkheden met betrekking tot de nulpunten, en deelbaarheidsvoorwaarden die voortvloeien uit het bestaan van t-designs in perfecte codes (zie (B), (C)), maar die zijn niet sterk genoeg om substantieel bij te dragen tot een volledige oplossing van het probleem.

Merk op dat (n,q)=(11,3) voldoet (de 'Golay parameters', zie (B)). Natuurlijk voldoen ook (2,2) (triviale code) en (5,2) (repetitiecode). Er zijn nooit andere oplossingen met e=2 en n>5 gevonden. We willen graag bewijzen dat er geen andere zijn.

3. H e r f o r m u l e r i n g (voor oneven q)

Om eens anders tegen het probleem aan te kijken, schrijven we n-x = y.
(2.2) wordt dan:

(3.1) --- q² y² - (q² - 4q + 2nq)y + (n-1)(n-2) heeft twee gehele nulpunten y1 en y2, waarbij

(3.2) --- y1 + y2 = 1 + 2(n-2)/q en y1 y2 = (n-1)(n-2)/q².

We gaan voortaan uit van oneven q, het eenvoudigste geval mbt (3.2).
Uit (3,2) volgt dan dat een natuurlijk getal k bestaat zo dat

(3.3) --- n = 2 + k q².

De discriminant van (3.1) is dan
(y1 - y2)² = (y1 + y2)² - 4 y1 y2 = 1 + 4k(q-1), dus er bestaat een natuurlijk getal m met
1 + 4k(q-1) = (2m+1)², ofwel

(3.4) --- k(q-1) = m(m+1).

Met (3.3) en (3,4) gaat de bolpakkingsvoorwaarde (2.1) dan over in

(3.5) --- 1 + (1/2)m(m+1)(3q - 1 + m(m+1)q²) deelt qⁿ

(voor m=1 en q=3 krijgt men de Golay parameters).
Uit (3.4) blijkt

(3.6) --- q is kleiner dan 2(m+1)².

Voor oneven q zijn de voorwaarden (3.5) en (3.6) ongeveer even sterk als (2.1) en (2.2). Maar wat kan men er mee?

4. V e r v o l g o n d e r z o e k (oneven q)

We zoeken naar (m,q) die voldoen aan (3.5) en (3.6).
Als een priemgetal p het linkerlid van (3.5) deelt, dan volgt uit voorwaarde (3.5) dat p ook q deelt, dus

(4.1) --- p deelt m(m+1) - 2 (en p is niet 2, omdat q oneven is).

Voor gegeven m krijgt men nu soms de eis dat het linkerlid van (3.5) een priemmacht is. Dit blijkt uit het volgende lijstje van mogelijke combinaties (m,p):

(4.2) ---

m: 3 4 5 6 7 8 9 10 11 12 13 14

p: 5 3 7 5 3 5,7 11 3 5,13 7,11 3,5 13

Bijvoorbeeld, voor m=7 vindt men

(4.3) --- (-3³) + (2² 3 7 q) + (2⁵ 7² q²) = 3² (q een natuurlijke getallen kleiner dan 128),

en men controleert dat zo'n q niet bestaat.

Aldus is het onderzoek voor elke vaste m eenvoudig (voor vaste q is het moeilijker, zie ook (C)).
Van de andere kant, zo'n p is voor elke m weer anders, en vaak is er meer dan één mogelijke p (zie (4.2));
en men kan niet algemeen uitsluiten dat het linkerlid van (3.5) voor een of andere m en een of andere q kleiner dan 2(m+1)² weinig verschillende priemfactoren bevat.

Het is dus mogelijk dat de kwestie in de toekomst een heel oude kwestie zal worden.

5. L i t e r a t u u r

(A) MR Best : On The Existence Of Perfect Codes; Mathematisch Centrum Amsterdam 1978

(B) JH van Lint : Coding Theory; Springer Verlag Berlin etc 1973

e-mail: info@petericepudding.com (ik open geen bijlagen)

klik hier om terug te gaan naar mijn hoofdpagina

extended investigations