Frequency squares and affine designs

V C Mavron Department of Mathematics, University of Wales, Aberystwyth, SY23 3BZ U.K.

vcm@aber.ac.uk

Submitted: May 17, 2000; Accepted: November 22, 2000.

Abstract

The known methods for constructing complete sets of mutually orthogonal frequency squares all yield one of two parameter sets. We show that almost all these constructions can be derived from one basic design theory construction.

Key words: Matrices, block designs, orthogonal arrays, Latin squares. AMS subject classifications: Primary 05B20, Secondary 05B05, 05B15.

1 Introduction

Frequency squares are an extension of the concept of latin squares. Investigations have centred on finding analogues to Bose’s theorem: a set of mutually orthogonal n × n latin squares has at most n − 1 squares. The set is complete if it has n − 1 squares.

Laywine and Mullen ([8], [9]) have investigated frequency squares from this viewpoint. See also [2] for an account. There are at present only two known parameter sets of complete sets of mutually orthogonal frequency squares (MOFS). We shall show that most of the known constructions may be obtained through just one general design theory construction involving parallel classes of lines in affine designs.

More detailed information on basic design theorems, definitions and terminology used in this paper may be found in [1], [2], [3] and [9]. Here we give a brief outline.

Let D be a 1-(v, k, r) design, with v points, k points on each block, b blocks and r blocks on each point. If the blocks of D can be partitioned into r subsets of m = v/k disjoint blocks, called parallel classes, then D is resolvable. In this case, if further any two blocks from different parallel classes (i.e. non-parallel blocks) meet in a constant number μ points, then μ = k/m and D is said to be affine, or D is an (m, r; μ) net.

Suppose D is affine. If the dual design D^{∗} of D (which is a 1-(b, r, k) design) is resolvable, then it can be shown that r ≤ k ([1], [11], [12]) with equality if and only if D^{∗} is also affine. When D, D^{∗} are both affine then b = v = μm^{2} and r = k = μm and D is called a symmetric (μ, m)-net.

Note that transversal designs are just the duals of affine designs.

An n × n matrix F is a frequency square of type F (n, μ) over an m-set S if each element of S occurs with frequency μ (= n/m) in each row and each column. Thus F is a latin square when μ = 1.

Two n × n frequency squares over S are orthogonal if when one is superimposed on the other, each ordered pair from S × S occurs exactly μ^{2} times. (This clearly agrees with the idea of orthogonality in latin squares.)

We remark that there is a more general definition for frequency squares which allows the frequencies of different elements of S to differ.

Hedeyat et al [5] showed that a set of type F (μm, μ) MOFS has at most (μm − 1)^{2}/(m − 1) squares. The set is complete if it has this many squares.

According to [2], the only complete sets of MOFS known are of type F (n, μ) with either: (i) m a prime power and n a power of m; or (ii) n = 2m is the order of a Hadamard matrix, where n = μm.

2 A construction

The construction described here for complete sets of MOFS is based on a technique for constructing affine 2-designs with parallel classes of lines.

A line in an affine 2-(μm^{2}, μm, (μm − 1)/(m − 1)) design D is the intersection of all blocks containing two given points. Thus a line L is contained in exactly λ = (μm − 1)/(m − 1) blocks. A block B is parallel to L if B is parallel to a block containing L. (So B either contains L or misses L.) A parallel class is parallel to L if some (and hence every) block in it is parallel to L.

Thus a line is parallel to exactly λ parallel classes. We say two lines are parallel if they are parallel to the same λ parallel classes.

It is well known and easy to prove that a line L has at most m points; and L has exactly m points if and only if each block not parallel to L meets L in a point.

Theorem 1 If there exists an affine 2-(μm^{2}, μm, (μm−1)/(m−1)) design with a parallel class of lines, then there exists a complete set of MOFS of type F (μm, μ).

Proof. Let the affine 2-design be Γ and let L = {L_{1}, L_{2}, ..., L_{μm}} be a parallel class of lines.

Choose any parallel class of blocks E = {E_{1}, E_{2}, ..., E_{m}} of Γ not parallel to L. Let E_{j} meet L_{i} in the point L_{ij} (1 ≤ i ≤ m; 1 ≤ j ≤ μm). Then each point of Γ is uniquely expressible in the form L_{ij}.

Choose X from any of the λ = (μm − 1)/(m − 1) parallel classes that are parallel to L. Now Γ has r = (μm^{2} − 1)/(m − 1) parallel classes and so has r − λ = μm not parallel to L. Choose Y from any of the μm − 1 parallel classes not parallel to L,where Y ≠ E. Then we define a frequency square F = F (X, Y) as follows.

Given i, j where 1 ≤ i, j ≤ μm, then F_{ij} is determined thus. Let X_{t} (1 ≤ t ≤ m) be the unique block of X containing the line L_{i}. Then if the block in Y on L_{jt} is Y_{α} (1 ≤ α ≤ m), we define F_{ij} = α.

We show F is a frequency square of type F (μm, μ). Given j (1 ≤ j ≤ μm) and α (1 ≤ α ≤ m), we count i for which F_{ij} = α. Now if L_{jt} is the unique point of L_{j} on Y_{α}, then L_{i} can be any of the μ lines of L contained in X_{t}. So there are μ values of i.

Next, given 1 ≤ i ≤ μm and α, let X_{t} be the unique block of X containing L_{i}. Then for F_{ij} = α, we can choose L_{j} to be any of the μ lines in the intersection of E_{t} and Y_{α}. It follows that α appears μ times in each row and column of F. So F is a frequency square as required.

Consider another such frequency square F′ = F (X′, Y′), where either X ≠ X′ or Y ≠ Y′. We shall show that F and F′ are orthogonal.

Given α, β (1 ≤ α, β ≤ m), consider the simultaneous equations in i and j: F_{ij} = α,

Fij^{′} = β.

There are two cases to examine:

Case X ≠ X′: Then λ > 1 and so μ > 1. Choose any j (1 ≤ j ≤ μm). Let Y_{α} and Y′_{β} meet the line L_{j} at L_{jt} and L_{ju}, respectively. In Γ, X_{t} and X′_{u} meet in μ points, and hence in μ/m lines of L. If L_{i} is any of these lines, then the above equations both hold. Case X = X′: Then Y ≠ Y′. Let L_{jt} be any of the μ points in which Y_{α} meets Y′_{β}. Choose i so that L_{i} is one of the μ lines of L contained in X_{t}. Then again the equations both hold.

Therefore F and F′ are orthogonal. It follows that by varying X and X′ we get a complete set of type F (μm, μ) MOFS.

Observe that in the case μ = 1, Γ is an affine plane of order m and the theorem gives a complete set of n − 1 MOLS of order n.

Affine 2-designs with parallel classes of lines can be constructed using the following result (see [11], [14], [12] or [6]).

Theorem 2 The symmetric subnets of an affine 2-design are in one-to-one correspondence with its parallel classes of lines. There exists an affine 2-(μm, μ, (μ − 1)/(m − 1)) design and a symmetric (μ, m)-net if and only if there exists an affine 2-(μm^{2}, μm, (μm − 1)/(m − 1)) design with a parallel class of lines.

Using this theorem we easily deduce the following corollary to Theorem 1.

Corollary 3 If there exists an affine 2-(μm, μ, (μ−1)/(m−1)) design and a symmetric (μ, m)-net, then there exists a complete set of MOFS of type F (μm, μ).

Remark 4 It is well known (see [1] or [2], for instance) that the existence of a symmetric (μ, m)-net is equivalent to that of a generalized Hadamard μm × μm matrix over a group of order m.

In particular it follows from this remark, putting m = 2, that the existence of a symmetric (μ, 2)-net is equivalent to that of a Hadamard matrix of order 2μ.

Using this connection between symmetric nets and Hadamard matrices we obtain the next result.

Theorem 5 If there is a Hadamard matrix of order 2μ, then there is a 2-(4μ, 2μ, 2μ − 1) design with a parallel class of lines. (The design is necessarily affine and is in fact a 3-(4μ, 2μ, μ − 1) design.)

Proof. From Remark 4 we deduce the existence of a symmetric (μ, 2)-net. It is well known (see [1], [2] or [15]) that the existence of a Hadamard matrix of order n implies that of 2-(4μ, 2μ, 2μ − 1) design which is necessarily affine and a 3-design. Now apply Theorem 2.

Remark 6

(a) A comparison of Theorems 2.1 and 2.2 suggests, broadly speaking, that the existence of a symmetric (μ, m)-net is equivalent to that of a complete set of type F (μm, μ) MOFS, perhaps under some extra conditions.

(b) It is well known (see [1], [2] or [15]) that the existence of a Hadamard matrix of order 2μ implies that of a Hadamard matrix of order 4μ by the ‘doubling’ method, and that the existence of a Hadamard matrix of order 4μ implies that of a design with the parameters given in Theorem 2.5. However, Theorem 5 guarantees the existence of a parallel class of lines in the design.

Now we can show how Theorem 1 implies some of the known and perhaps some new ways of looking at constructions of complete sets of MOFS.

1. If we take Γ in Theorem 1 to be the affine design formed by the points and hyperplanes of the n-dimensional affine space over GF (m) and choose any of its parallel classes of lines, we obtain complete sets of MOFS of type F (m^{n−1}, m^{n−2}) for any prime power m. This technique seems to be new.

2. ([2, IV.20.2, Theorem 20.8(4)]). Given an affine 2-(m^{2h}, m^{2h−1}, (m^{2h−1} − 1)/ (m − 1)) design D (i.e. an AD(m^{2h−1}, m)) of dimension at least 2h − 2, (see [10] or [13] for definitions), let C_{1}, C_{2}, …, C_{2h−1}, be independent classes where C_{1}, C_{2}, …, C_{2h−2} are prime. Then for any choice of representatives c_{i} ∈ C_{i} (1 ≤ i ≤ 2h − 1), the intersection of the c_{i} is a line of size m of D. Thus we get m^{2h−1} disjoint lines of size m which are evidently parallel. Hence we have a parallel class of lines in D. Hence Theorem 1 applies, giving a complete set of MOFS of type F (m^{2h−1}, m^{2h−2}).

3. Street [14] showed there exists a complete set of type F (μm, μ) MOFS if there is a generalized Hadamard μm × μm matrix over a group of order m, and an affine 2-(μm, μ, (μ − 1)/(m − 1)) design. We can deduce this as follows. The existence of a symmetric (μ, m)-net follows from Remark 4. Then, from Theorem 2, Corollary 3 and Remark 4 we deduce that there exists a complete set of F (μm, μ) MOFS.

Remark 7 There exist symmetric nets which cannot be constructed from generalized Hadamard matrices (see Mavron and Tonchev [12]). Thus Corollary 3 extends Street’s result.

Remark 8 Laywine [7] constructs an affine 2-design which is not obtainable from a family of MOFS. Then Remark 6 suggests that the affine design does not have a symmetric subnet. However, this is not immediately obvious and further investigation of the relationship between nets and MOFS is needed as well as an analysis of Laywine’s construction.

4. Federer [4] showed that there is a complete set of MOFS of type F (2μ, μ) if there is a Hadamard matrix of order 2μ.

As a parameter existence result, we can deduce it from Theorems 1 and 5.

Before giving the next existence result for complete sets of MOFS, we state the following theorem from Mavron [11].

Theorem 9 If there exists an affine plane of order m and an affine 2-(μm, μ, (μ − 1)/(m − 1)), then there exists a symmetric (μ, m)-net.

5. ([2, IV.20.2, Theorem 20.8(5)]) Suppose there exists an affine plane of order m and an affine 2-(μm, μ, (μ − 1)/(m − 1)) design. Then there exists a complete set of type F (μm, μ) MOFS.

This can be obtained from Theorem 1 in the following way. From Theorem 8 we have the existence of a symmetric (μ, m)-net, and hence from Corollary 3 the existence of the MOFS.

References

[1] T Beth, D Jungnickel, H Lenz: Design Theory, 2nd edition (Cambridge University Press, 1999).

[2] C J Colbourn, J H Dinitz (eds.), The CRC Handbook of Combinatorial Designs (CRC Press, 1996).

[3] J Denés, A D Keedwell: Latin Squares: New Developments in the Theory and Applications (Elsevier, 1991).

[4] W T Federer: On the existence and construction of a complete set of orthogonal F (4t; 2t, 2t)-square designs, Ann. Statistics, 5 (1977), 561-564.

[5] A Hedeyat, D Raghavarao, E Seiden: Further contributions to the theory of F - squares design, Ann. Statist. 3, (1975), 712-716.

[6] D Jungnickel, S S Sane: On existence of nets, Pacific J. Math. 103 (1982), 437-455.

[7] C F Laywine: An affine design with v = m^{2h} and k = m^{2h−1} not equivalent to a complete set of F (m^{h}; m^{h−1}) MOFS, J. Combin. Designs 7 (1999), 331-340.

[8] C F Laywine, G L Mullen: Generalizations of Bose’s equivalence between complete sets of mutually orthogonal latin squares and affine planes, J. Comb. Theory A, 61 (1992), 13-35.

[9] C F Laywine, G L Mullen: Discrete Mathematics Using Latin Squares (Wiley, 1998).

[10] V C Mavron: On the structure of affine designs, Math. Z. 125 (1972), 298-316.

[11] V C Mavron: Translations and parallel classes of lines in affine designs, J. Comb. Theory A, 22 (1977), 322-330.

[12] V C Mavron, V D Tonchev: On symmetric nets and generalized Hadamard matrices from affine designs, J. Geom. 67 (2000), 180-187.

[13] S S Shrikhande: Affine resolvable balanced incomplete block designs: a survey, Aequat. Math. 14 (1976), 251-269.

[14] D J Street: Generalized Hadamard matrices, orthogonal groups and F -squares, Ars. Comb. 8 (1979), 131-141.

[15] S Ud Din, V C Mavron: On designs constructed from Hadamard matrices, Proc. London Math. Soc. (3), 49 (1984), 274-288.