Crooked Functions, Bent Functions, and Distance Regular Graphs

T.D. Bending D. Fon-Der-Flaass

School of Mathematical Sciences, Queen Mary and Westfield College, London E1 4NS, U.K.

          T.Bending@mdx.ac.uk    d.g.flaass@writeme.com

Submitted: March 25, 1998; Accepted: June 30, 1998.

1991 Mathematical Subject Classification: 05E30, 05B20

Abstract

Let V and W be n-dimensional vector spaces over GF (2). A mapping Q : V → W is called crooked if it satisfies the following three properties:

Q(0) = 0;

Q(x) + Q(y) + Q(z) + Q(x + y + z) ≠ 0 for any three distinct x, y, z; Q(x) + Q(y) + Q(z) + Q(x + a) + Q(y + a) + Q(z + a) ≠ 0 if a ≠ 0 (x, y, z

arbitrary).

We show that every crooked function gives rise to a distance regular graph of diameter 3 having λ = 0 and μ = 2 which is a cover of the complete graph. Our approach is a generalization of a recent construction found by de Caen, Mathon, and Moorhouse. We study graph-theoretical properties of the resulting graphs, including their automorphisms. Also we demonstrate a connection between crooked functions and bent functions.

1 Crooked functions and bent functions

Let V and W be n-dimensional vector spaces over GF(2), and Q : V → W any mapping. We shall use the notation

Q(a_{1}, a_{2}, …, a_{m}) = Q(a_{1}) + Q(a_{2}) + … + Q(a_{m}).

Also, for 0 ≠ a ∈ V, we denote by H_{a}(Q), or simply H_{a}, the set

H_{a} = H_{a}(Q) = {Q(x) + Q(x + a) | x ∈ V }.

We shall denote the size of a finite set X either by |X| or by #X; whichever notation looks better in the context.

DEFINITION 1 A mapping Q : V → W is called crooked if it satisfies the following three properties:

(1.1) Q(0) = 0;

(1.2) Q(x, y, z, x + y + z) ≠ 0 for any three distinct x, y, z;

(1.3) Q(x, y, z, x + a, y + a, z + a) ≠ 0 if a ≠ 0.

If Q : V :→ W is a crooked function, and A ∈ GL(V), B ∈ GL(W) any two automorphisms then the function Q′ = BQA, Q′(x) = B(Q(A(x))) is also crooked. We shall call such functions Q and Q′ equivalent. Also, for every a ∈ V, the function Q′′(x) = Q(a, x + a) is also crooked. We say that Q′′, and every function equivalent to Q′′, is affine equivalent to Q.

PROPOSITION 2 If Q is a crooked mapping then (2.1) Q is a bijection; (2.2) Every set H_{a}(Q) is the complement of a hyperplane; (2.3) The sets H_{a} are all distinct; in particular, every complement of a hyperplane

appears among them exactly once.

Moreover, every mapping Q satisfying property (2.2) above, and such that Q(0) = 0, is crooked.

PROOF. (2.1) follows immediately from property (1.3): if Q(x) = Q(y) for some x ≠ y, then, setting a = x + y, we have Q(x, x, x, x + a, x + a, x + a) = 0, contrary to (1.3).

Now we shall prove (2.2) and (2.3).

Condition (1.2) can be reformulated as follows: for a ≠ 0 and {x, x + a} ≠ {y, y + a} the elements Q(x) + Q(x + a) and Q(y) + Q(y + a) are distinct; or, equivalently, |H_{a}| = |V |/2. Condition (1.3) is equivalent to saying that the sets H_{a} are sum-free.

Obviously, complements of hyperplanes satisfy both these properties; therefore (2.2) together with Q(0) = 0 imply that Q is crooked.

Conversely, let H be a sum-free set of size |V |/2, and K = {x + y | x, y ∈ H}. Fix also any element h ∈ H, and let K_{0} = {h + x | x ∈ H}. H being sum-free means that H ∩ K = ∅, and since |K| ≥ |K_{0}| = |H| = |V |/2, we have |K| = |V |/2, and K = K_{0} = V \ H. The set K is closed under addition, since K + K = K_{0} + K_{0} ⊆ K, and therefore it is a hyperplane.

Finally, suppose that H_{a} = H_{b} for some a ≠ b, and K = V \H_{a}. Then for every x we have Q(x)+Q(x+a+b) = Q(x)+Q(x+a)+Q(x+a)+Q(x+a+b) ∈ H_{a}+H_{b} = K; and therefore H_{a+b} ⊆ K, which is impossible. □

Let Q : V → W be a crooked function, dimV = n. Let 0 ≠ a ∈ V. We define a linear functional h_{a} on W, and a mapping Q_{a} : V → GF(2), by the following rules:

h_{a}(w) = 1 if and only if w ∈ H_{a}(Q);

Q_{a}(v) = h_{a}(Q(v)).

PROPOSITION 3 The dimension of V is odd, n = 2m + 1.

For any hyperplane U ⊂ V, and any 0 ≠ a ∈ V, the set {u ∈ U | Q_{a}(u) = 1} is of size 2^{n−2} if a ∈ U, and of size 2^{n−2} ± 2^{m−1} if a ∉ U.

PROOF. Suppose first that a ∉ U. Let the function Q_{a} on U take the value 1 at x points, and the value 0 at y points, x + y = 2^{n−1}. Then on V \ U it takes the value 1 at y points, and the value 0 at x points.

For any v ∈ V, by (2.3) we have |H_{v} ∩ H_{a}| = |H_{v}|/2 = 2^{n−2}. Elements of this intersection correspond to pairs {x, x + v} ⊂ V such that Q_{a}(x) = 0, Q_{a}(x + v) = 1. Summing over all non-zero elements of U we get:

2xy = (|U| − 1)|H_{v} ∩ H_{a}| = (2^{n−1} − 1)2^{n−2}.

Now x, y are the roots of the quadratic equation

z^{2} − 2^{n−1}z + (2^{n−1} − 1)2^{n−3} = 0;

x, y = 2^{n−2} ± 2^{(n−3)/2}. Therefore n must be odd, and also the second equality of the proposition is proved. A similar argument proves the first equality. □

As the sizes of the sets in Proposition 3 suggest, crooked functions are closely related to quadrics, or more generally to Rothaus’ bent functions [R], which we now explore. We will consider functions F : V → GF(2), and will often identify such a function with its support (the set of points on which it takes the value 1), so that we can write |F | (or #F) to mean the size of F ’s support, for example.

DEFINITION 4 A mapping F : V → GF(2) is called bent if for every linear function L : V → GF(2) we have |F + L| = 2^{n} ± 2^{n/2}.

Clearly if F is a bent function on V then n must be even. As with crooked functions if A ∈ GL(V) then F′ = F A is bent. Also if a ∈ V then F′′(x) = F (x + a) is bent, and if L is linear then F′′′ = F + L is bent — these three operations all preserve bentness because they map linear functions to linear functions and hence preserve the condition in Definition 4. We say that two bent functions related by any combination of these three operations are equivalent. Note that every non-singular quadratic function is bent, so bent functions exist for all even n.

Extending the summation notation introduced above, we write F (^{•}, ^{•} + a) to mean {F (x, x + a) | x ∈ V }, and so on. The following useful characterisation of bent functions is quite straightforward:

LEMMA 5 F is bent iff for all non-zero a ∈ V we have #F (^{•},^{•} + a) = 2^{n−1}. □

We can now describe the connection between bent functions and crooked functions.

PROPOSITION 6 With the above notation, if 0 ≠ a ∈ V then for any hyperplane U ⊂ V not containing a:

(6.1) The two functions obtained by restricting Q_{a} to U and to V \ U are complementary, in the sense that we can translate one to the complement of the other.

(6.2) The function Q_{a}|_{U} is bent.

PROOF. First, remark that for all x ∈ V we have Q(x, x+b) ∈ H_{a} iff Q_{a}(x, x+ b) = 1.

(6.1) For all x ∈ V, Q(x, x + a) is certainly in H_{a}, so by the above remark Q_{a}(x) ≠ Q_{a}(x+a) and hence the two restrictions Q_{a}|_{U} and Q_{a}|_{V \U} are complementary via translation through a.

(6.2) Fix a vector b ∈ U. Using (6.1), and the same argument applied to Q_{a}(^{•} +b),

#Q_{a}|_{U}(^{•}, ^{•} + b) = \frac{1}{2}#Q_{a}(^{•}, ^{•} + b).

Now by the remark Q_{a}(x, x + b) = 1 iff Q(x, x + b) ∈ H_{a}, and the number of such x is 2|H_{a} ∩ H_{b}| = 2^{n−1}. Hence #Q_{a}|_{U}(^{•}, ^{•} + b) = 2^{n−2}, but b was arbitrary in U, so by Lemma 5 Q_{a}|_{U} is bent. □

We call a function such as Q_{a} which is composed of a bent function and its complement in this way quasibent. Given a quasibent function there is a unique translation (the vector a above) which takes it to its complement, which we call the function’s associated vector. Translation through any other vector produces a function agreeing with the original one on exactly half the domain, by Lemma 5.

In Proposition 6 we had a choice of the hyperplane U, and different choices lead to different bent functions Q_{a}|_{U}. However, note that the bent functions corresponding to the various choices differ by linear functions, so are equivalent.

DEFINITION 7 A set of 2^{n−1} quadratic forms V → GF(2) is called a Kerdock set if the sum of every two of them is non-singular.

By considering bilinear forms corresponding to the quadratic functions in a Kerdock set it is easy to show that such a set is maximal.

We write RM_{k} to denote the kth order Reed-Muller code, consisting of the supports of all functions V → GF(2) of degree at most k. A Kerdock set K induces a Kerdock code consisting of the cosets of the RM_{1} represented by the functions in K. A Kerdock code is a subcode of RM_{2}, and with the above assumption it contains RM_{1}. It has (length, size, minimum distance) parameters (2^{n}, 2^{2n}, 2^{n−1} − 2^{n/2−1}) — see [CvL, Chapter 12], for example.

However, if we wish to construct a code with these parameters as the union of various cosets of RM_{1}, it is not necessary for the differences between the representative functions to be non-singular quadratics — by Definition 4 it is enough that they are bent.

Thus we call a set of functions a bent Kerdock set if the sum of every two of them is bent. As before without loss of generality we may assume that the constant-0 function is in the set and hence that all the other functions are themselves bent. Similarly we can define a quasibent Kerdock set — note that in such a set all the quasibent functions have different associated vectors, for if two functions have the same associated vector their sum is fixed by translation through that vector, so isn’t quasibent, so must be the constant-0 function.

The point is that a true Kerdock code has maximal size given its length and minimum distance, among codes in RM_{2} which contain RM_{1}. However, a bent Kerdock set allows us to go outside RM_{2}. Since the bilinear forms argument does not apply we may be able to find such a set with more than 2^{n−1} functions, and hence obtain a larger code than we can obtain from a true Kerdock set.

DEFINITION 8 (8.1) A set of functions is called closed if the sum of every two functions in the set is also in the set.

(8.2) A set of functions V → GF(2) is called normal if every function maps 0 ∈ V to 0 ∈ GF(2).

If we add the constant-1 function to a quasibent function it remains quasibent, so by doing this where necessary we can make a quasibent Kerdock set normal. By considering the values the functions take on 0 it is clear that this normalisation will preserve closure.

Now, setting Q_{0} ≡ 0, we have

PROPOSITION 9 {Q_{a}}_{a∈V} is a closed normal quasibent Kerdock set.

PROOF. Closure: Pick a, b ≠ 0. (Q_{a} + Q_{b})(x) = 1 iff Q(x) is in exactly one of H_{a}, H_{b}. These sets are complements of hyperplanes, so their symmetric difference is also the complement of a hyperplane, and by (2.3) it is some H_{c}. Thus (Q_{a} + Q_{b})(x) = 1 iff Q(x) ∈ H_{c} iff Q_{c}(x) = 1, so that Q_{a} + Q_{b} = Q_{c}.

Normality: Pick a ≠ 0. H_{a} is a hyperplane complement so Q(0) = 0 ≠ H_{a} so Q_{a}(0) = 0. □

It turns out that the converse is true as well:

PROPOSITION 10 If K is a closed normal quasibent Kerdock set then there exists a crooked function Q which induces K via Proposition 9.

PROOF. K is closed under addition, and contains 2^{n} functions, so is an ndimensional subspace of the space of functions V → GF(2). Label the functions in K with the points of V by picking a basis {e_{1}, …, e_{n}} for V and a corresponding basis {Q_{e_{1}}, …, Q_{e_{n}}} for K, and then extending linearly. Similarly, let H_{e_{i}} denote the hyperplane complement consisting of vectors in V whose dot product with e_{i} is 1, and then extend this labelling linearly to every hyperplane complement H_{v}.

Now define Q(x) = (Q_{e_{1}}, …, Q_{e_{n}}) with respect to our chosen basis for V. By normality Q(0) = 0. Now if we pick a, b ∈ V and write b = ∑_{i} λ_{i}e_{i} then

Q(v, v + a)  ∈ H_{b}
⟺  ∑_{i} Q_{e_{i}}(v, v + a)e_{i}  ∈ ∑_{j} λ_{j}H_{j}
⟺ ∑_{i} ∑_{{j:e_{i}∈H_{j}}} Q_{e_{i}}(v, v + a)λ_{j} = 1
⟺  ∑_{i} Q_{e_{i}}(v, v + a)λ_{i}  = 1
⟺  Q_{b}(v, v + a)  = 1

If b = a then this last equality is true for all v because Q_{a} is quasibent, so {Q(^{•}, ^{•} + a)} ⊆ H_{a}. Otherwise the last equality is true for exactly half the possible values of v, hence so is the first equality. Each value of Q(v, v + a) occurs for two choices of v, so

#\{Q(^{•}, ^{•} + a) ∩ H_{b}\} = 2^{n−2} = \frac{1}{2}|H_{b}|

Since this is true for all b ≠ a the set {Q(^{•}, ^{•} + a)} must be the whole of H_{a}. Thus Q is crooked as required, and it’s a straightforward check that Q induces the original set K. □

Note that if we compose Q with a linear map A we obtain a crooked function AQ which induces the same family of quasibent functions as Q, so this reconstruction cannot be unique. In fact it is not even clear whether the reconstruction is unique up to such a composition.

We might hope to use a quasibent Kerdock set to construct a bent Kerdock set. Consider an odd-dimensional space V embedded as a subspace of codimension 1 in a space W. If we have a quasibent function Q_{a} on V we can extend it to a bent function on W, as follows. Suppose Q_{a} has associated vector a, and as before pick a hyperplane U in V not containing a. U has two cosets U and U + a in V, and another two cosets U + b and U + a + b, say, in W \ V. Define a function

Q̂_{a}(x) = \{ \begin{matrix}Q_{a}(x) & if x ∈ U or x ∈ U + a \\ Q_{a}(x + b) & if x ∈ U + b \\ Q_{a}(x + a + b) & if x ∈ U + a + b. \end{matrix}

Thus Q̂_{a} consists of four copies of the bent function Q_{a}|_{U}, except that the copy on U + a has been inverted (recall that Q|_{U} and Q|_{U+a} are complementary). Then Q̂_{a} is a bent function on W — see [R], for example.

So given a crooked function Q we can construct a closed quasibent Kerdock set {Q_{a}}, and we’d like to extend these functions to form a closed bent Kerdock set {Q̂_{a}}. The simplest way to ensure closure of {Q̂_{a}} after the extension from V to W is to pick the hyperplanes U such that for all distinct a, b, c we have

Q_{a} + Q_{b} = Q_{c} ⇒ Q̂_{a} + Q̂_{b} = Q̂_{c}.

If we write U_{a} for the hyperplane used to extend Q_{a} then from the definition of Q̂_{a} it’s enough to ensure that

Q_{a} + Q_{b} = Q_{c} ⇒ \overline{U_{a}} + \overline{U_{b}} = \overline{U_{c}}.

However, recall that associated with a crooked function Q we already have an indexed set of hyperplane complements {H_{a}} such that

H_{a} + H_{b} = H_{c} ⇒ Q_{a} + Q_{b} = Q_{c}.

Thus we are looking for an indexed set of hyperplane complements \{\overline{U_{a}}\} such that a ∈ \overline{U_{a}} for all a and for all distinct a, b, c we have

H_{a} + H_{b} = H_{c} ⇒ \overline{U_{a}} + \overline{U_{b}} = \overline{U_{c}}.

If we define a map φ : H_{a} ↦ \overline{U_{a}} then it is a straightforward check that this last condition is satisfied iff φ is linear. But in this case {φH_{a}} is just the set of H_{a}s associated with the crooked function φQ. Thus finding a suitable set of \overline{U_{a}}s corresponds to finding a linear image of the original Q such that a ∈ H_{a} for all a.

We now need some examples of crooked functions to work with.

PROPOSITION 11 Let ∗ : V × V → V be a bilinear multiplication satisfying (i) x ∗ x ≠ y ∗ y for x ≠ y; and (ii) x ∗ y ≠ y ∗ x for x, y linearly independent.

Then Q(x) = x ∗ x is crooked.

The converse also holds: if ∗ is a bilinear multiplication such that Q(x) = x ∗ x is crooked then this multiplication satisfies (i) and (ii).

PROOF. In one direction: let ∗ satisfy (i) and (ii).

Condition (1.1) is trivially satisfied.

Condition (1.2): the elements x + y and x + z are linearly independent, therefore

x ∗ x + y ∗ y + z ∗ z + (x + y + z) ∗ (x + y + z) = (x + y) ∗ (x + z) + (x + z) ∗ (x + y) ≠ 0,

by (ii).

Condition (1.3):

x ∗ x + y ∗ y + z ∗ z + (x + a) ∗ (x + a) + (y + a) ∗ (y + a) + (z + a) ∗ (z + a)

= (x + y + z) ∗ (x + y + z) + (x + y + z + a) ∗ (x + y + z + a) ≠ 0,

by (i).

In the opposite direction: suppose that Q(x) = x ∗ x is crooked. The condition (i) follows from (2.1). Take any two distinct non-zero vectors x, y. We have

x ∗ y + y ∗ x = Q(0, x, y, x + y) ≠ 0

by (1.2), thus proving the condition (ii). □

Examples of such a multiplication can be constructed as follows: take V = GF(2^{n}), n odd, take k coprime to n, and let x ∗ y = x · y^{2^{k}}. Thus we get the examples constructed by de Caen et al. in [dCMM]. Actually, these are the only examples of crooked functions known at present. In particular, it is unknown if there exist crooked functions which don’t come from a bilinear multiplication.

Unfortunately, given any crooked function Q with n ≤ 9 constructed by Proposition 11 there is no linear image of Q satisfying a ∈ H_{a} for all a, so in these cases we cannot construct a closed bent Kerdock set as suggested above.

We conclude this section with a characterization of crooked functions constructed by Proposition 11.

PROPOSITION 12 A crooked function Q comes from a bilinear multiplication if and only if

(∗) for every 3-dimensional affine subspace U ⊆ V

Q(U) = ∑_{u∈U} Q(u) = 0.

PROOF. Let dim V = dim W = n. Let C be the set of all functions Q : V → W satisfying both (∗) and the condition (1.1) of Definition 1, which is simply Q(0) = 0. Let also M be the set of all bilinear maps f : V × V → W, and M_{0} = {f ∈ M | f(x, x) = 0 for all x ∈ V }. The sets C, M, and M_{0} are vector spaces over GF(2). It is easy to check that for every f ∈ M, the function Q(x) = f(x, x) is in C. Two functions f_{1}, f_{2} ∈ M give the same function from C if and only if they are in the same coset of M_{0}. So, to prove the theorem, we only need to check that dim C = dim M − dim M_{0}.

A function f ∈ M is uniquely determined by its n^{2} values f(e_{i}, e_{j}) on basis vectors; therefore dim M = n^{3}.

A function f ∈ M belongs to M_{0} if and only if for all x, y, f(x, y) = f(y, x), and f(e_{i}, e_{i}) = 0 for all basis vectors. Indeed, if f(x, x) ≡ 0 then for all x, y we have

f(x, y) + f(y, x) = f(x + y, x + y) + f(x, x) + f(y, y) = 0.

Conversely, if for all x, y we have f(x, y) = f(y, x) then the same equality implies that the function f(x, x) is linear; and if it is zero on the basis vectors then it is identically zero. Therefore an element f ∈ M_{0} is uniquely determined by the values f(e_{i}, e_{j}) for i < j, and it follows that dim M_{0} = n\binom{n}{2}.

Finally, the characteristic vectors of affine subspaces of dimension 3 generate the Reed-Muller code RM(n, n − 3) the dimension of which is equal to

\binom{n}{0} + \binom{n}{1} + … + \binom{n}{n − 3} = 2^{n} − 1 − n − \binom{n}{2}

(see, for example, [CvL, Chapter 12]). A function Q ∈ C is uniquely determined by n functions Q_{i} : V → GF(2), the coordinates of the values with respect to a basis of W. Each Q_{i} is orthogonal to RM(n, n − 3) and, in addition, Q_{i}(0) = 0. Therefore dim C = n(n + \binom{n}{2}). Now comparing the dimensions gives us the theorem. □

2 Crooked functions and rectagraphs

A rectagraph is a graph without triangles in which every pair of vertices at distance 2 lies in a unique 4-cycle. There are not too many constructions of rectagraphs known; especially rectagraphs of small diameter. In this section we show that every crooked function gives rise to a distance regular rectagraph of diameter 3.

Let Q : V → W be a crooked function. For a, b ∈ V, i, j ∈ GF(2) define

D(a, i; b, j) = Q(a + b) + (i + j + 1)Q(a, b).

Let G = G_{Q} be the graph on the vertex set V × GF(2) × W = {(a, i, α)}; vertices (a, i, α) and (b, j, β) are adjacent if and only if they are distinct, and

α + β = D(a, i; b, j).

PROPOSITION 13 The graph G_{Q} is distance regular with intersection array

(2^{n+1} − 1, 2^{n+1} − 2, 1; 1, 2, 2^{n+1} − 1)

— a distance regular 2^{n}-cover of the complete graph K_{2^{n+1}}.

PROOF. The sets F_{a,i} = {(a, i, α) | α ∈ W } will be the fibres of the cover. They are independent sets, since D(a, i; a, i) = Q(a + a) = 0 by (1.1). Any two fibres are joined by a 1-factor; therefore vertices in every fibre are at mutual distances three or more. We only need to show that G has parameters λ = 0 and μ = 2 — distance regularity will then follow by a simple counting argument. Add a loop at each vertex of G — this can be done by dropping the condition (a, i, α) ≠ (b, j, β) in the definition of G_{Q}. We need to show that in the resulting graph we have λ = μ = 2; or, that when (a, i) ≠ (b, j), the multiset

{D(a, i; x, k) + D(b, j; x, k) | x ∈ V, k ∈ GF(2)}

is the whole W taken with multiplicity 2.

Case 1. i ≠ j. We shall show that {D(a, i; x, i) + D(b, j; x, i) | x ∈ V } = W — this will suffice. It is enough to check that

D(a, i; x, i) + D(b, j; x, i) + D(a, i; y, i) + D(b, j; y, i) ≠ 0

for x ≠ y. The sum in question is equal to

Q(a, x, a + x, b + x, a, y, a + y, b + y)
= Q(x, x + (x + y), a + x, a + x + (x + y), b + x, b + x + (x + y)) ≠ 0

by (1.3).

Case 2. i = j. In this case a ≠ b. Let k = i + 1. We shall show that

{D(a, i; x, i) + D(b, i; x, i)} ∩ {D(a, i; x, k) + D(b, i; x, k)} = ∅, (i)

and that in both these multisets every element occurs twice — (ii) and (iii).

(i) Q(a, x, a + x, b, x, b + x, a + y, b + y) = Q(a, a + (a + b), a + x, a + x + (a + b), a + y, a + y + (a + b)) ≠ 0 by (1.3).

(ii) Let Q(a, x, a+x, b, x, b+x) = Q(a, y, a+y, b, y, b+y); then Q(a+x, b+x, a+ y, (a + x) + (b + x) + (a + y)) = 0. By (1.2), this happens in exactly two cases: when x = y, and when x = y + (a + b).

(iii) The same as (ii): Q(a + x, b + x, a + y, b + y) = 0 iff either x = y or x = y + (a + b).

The proposition is proved. □

We call graphs obtained from a crooked function by the above construction crooked graphs. Now we shall study structural properties of crooked graphs. We shall follow the lines of [dCMM] as far as possible; many of the arguments from that paper can be applied to our more general situation almost unchanged.

It is evident that equivalent crooked functions give rise to isomorphic graphs; linear transformations of V and W result only in renaming the fibres, and vertices in fibres.

Let G = G_{Q} be a crooked graph. Obviously, the parition of vertices into fibres is uniquely determined. Following [dCMM], call a set of four fibres a quad iff their union contains a subgraph isomorphic to the 3-cube. As the graph induced on any four quads has valency 3, the 3-cube must be one of its connected components.

Also, by pairs we mean the sets P_{a} = F_{a,0} ∪ F_{a,1} for a ∈ V, and by halves the sets H_{i} = ∪_{a∈V} F_{a,i} for i = 0, 1. The last two definitions, unlike the definition of a quad, depend on the presentation of G as a crooked graph; but we shall show that pairs and halves can be recovered from the graph structure only.

PROPOSITION 14 The quads are the sets of the form (i) {F_{a,i}, F_{b,i}, F_{c,i}, F_{a+b+c,i}} where a, b, c ∈ V are distinct, and i ∈ {0, 1}; and (ii) {F_{a,0}, F_{b,0}, F_{a,1}, F_{b,1}} where a, b ∈ V are distinct.

A set S of two fibres is a pair if and only if S together with an arbitrary third fibre is contained in a unique quad.

A set S of 2^{n} fibres is a half if and only if any three fibres in S are contained in a unique quad in S.

PROOF. Take a quad, and denote the vertices forming a cube by symbols [ijk], i, j, k ∈ {0, 1}, in the usual way. Each fibre contains two opposite vertices of the cube. Suppose, without loss of generality, that

[000] = (a, 0, α),

[011] = (b, 0, β). Then

[111] = (a, 0, β + Q(a, b, a + b)),

[100] = (b, 0, α + Q(a, b, a + b)). The other two fibres are those containing the two common neighbours of [000] and [011]; from the proof of Proposition 13, case 2, it follows that they are in the same half. Again, we need to consider two cases.

Case 1. α + β = Q(a + x, b + x) for some x ∈ V. Let y = x + a + b. Then we also have α + β = Q(a + y, b + y).

The coordinates of the remaining vertices now are:

[001] = (x, 1, α + Q(a + x)),

[010] = (y, 1, α + Q(a + y)),

[110] = (x, 1, β + Q(a, b, a + b, a + x)),

[101] = (y, 1, β + Q(a, b, a + b, a + y)).

They form the remaining two edges of the cube if and only if

Q(x, y, x + y) = α + β + Q(a, b, a + b, a + x, a + y)

which is equivalent to

Q(x, x + a + b, a, b) = 0.

By (1.2), this holds if and only if {x, y} = {a, b}, and we get the quads of type (ii).

Case 2. α + β = Q(a, b, a + x, b + x) for some x ∈ V. Then we also have α + β = Q(a, b, a+y, b+y) for y = x+a+b, and the four fibres are {(a, 0), (b, 0), (x, 0), (y, 0)}. An easy calculation shows that they indeed form a quad of type (i).

The last two claims of the proposition are taken unchanged from [dCMM, Lemma 2.6]. □

Note that the quads inside a half determine on the fibres in this half the structure of an affine space; and the affine structures determined in this way on the two halves are identical, which means that we can consider them as a single affine structure on the set of pairs.

Let A = AutG.

The mappings s_{γ} : (a, i, α) → (a, i, α + γ), γ ∈ W, are automorphisms of G, and comprise the whole kernel of the action of A on the fibres (see [GH, Lemma 7.3]); so the affine structure on each fibre is also uniquely determined. Let F = ⟨s_{γ} | γ ∈ W ⟩.

The automorphism z : (a, i, α) → (a, i + 1, α) is the unique automorphism interchanging the fibres inside each pair which has the additional property that every vertex v is adjacent to z(v). Therefore, z lies in the centre of A. The group P = ⟨F, z⟩ is the kernel of the action of A on the pairs.

PROPOSITION 15 Let G = G_{Q} = {(a, i, α)} be a crooked graph constructed from a crooked mapping Q : V → W, and c ∈ V. The following are equivalent:

(i) there exists another crooked labelling, [a, i, α], of G in which [0, 0, 0] = (c, 0, 0); (ii) there exists another crooked labelling, [a, i, α], of G in which [0, 0, 0] = (c, i, γ); (iii) For every 3-dimensional affine subspace U ⊆ V parallel to c

Q(U) = ∑_{u∈U} Q(u) = 0.

Moreover, then the crooked function corresponding to the new labelling is affine equivalent to Q.

PROOF. (i) and (ii) are clearly equivalent, since by the above remarks all vertices in the pair P_{c} are equivalent under the automorphism group.

Now, let [a, i, α] be a crooked labelling with the crooked function R, such that [0, 0, 0] = (c, 0, 0). Since the affine structure in fibres is invariant, me can assume without loss of generality that [0, 0, β] = (c, 0, β) for all β ∈ W. Since pairs are also invariant, we have [0, 1, β] = (c, 1, β) ([0, 1, β] being the unique neighbour of [0, 0, β] inside the pair).

Similarly, invariance of the affine structure on the set of pairs enables us to assume that, for every x ∈ V, β ∈ W, [x, i, β] = (x + c, i, γ) for some γ = γ(x, β) ∈ W.

To find γ, note that the vertices [0, i, β] = (c, i, β) and [x, i, β] = (x + c, i, γ) are adjacent. Therefore, β + γ = Q(x, c, x + c).

Now we know the new labels for all vertices:

[x, i, β] = (x + c, i, β + Q(x, c, x + c)).

The vertices [a, i, α] and [b, i, β] are adjacent, on one side, if and only if α + β = R(a, b, a + b). On the other side, these vertices are (a + c, i, α + Q(a, c, a + c)) and (b+c, i, β+Q(b, c, b+c)), and so are adjacent if and only if (after a simple calculation) α + β = Q(a, b, a + b). Therefore

R(a, b, a + b) = Q(a, b, a + b). (∗) Considering in the same manner the vertices [x, i, α] and [a + x, j, β] for i ≠ j, we

obtain R(a) = Q(a) + Q(x, x + c, x + a, x + a + c). (∗∗) Thus, for any a the value Q(x, x+c, x+a, x+a+c) = Q(a)+R(a) is independent

of x. Setting x = 0, we get R(a) = Q(c, a + c), so R is affine equivalent to Q.

To finish the proof, note that (∗∗) implies the assertion (iii) of the proposition; and (iii) together with R(a) = Q(c, a + c) imply both (∗) and (∗∗). □

3 Dimension 3

PROPOSITION 16 The crooked function of dimension 3 is unique up to equivalence. The corresponding crooked graph is vertex transitive.

PROOF. Note that Proposition 11 gives us at least one crooked function of dimension 3. Let Q : V → W be a crooked function of dimension 3. We shall denote elements of the spaces V and W by symbols (ijk) and [ijk], respectively (i, j, k ∈ {0, 1}). We have:

Q((000)) = [000].

The elements Q((001)), Q((010)), Q((011)) are non-zero, and have a non-zero sum. Therefore they are linearly independent, and without loss of generality we can assume that

Q((001)) = [001],
Q((010)) = [010],
Q((011)) = [100].

(Any other situation can be reduced to this one by a suitable linear transformation of W.) Similarly, applying a suitable transformation of V, we can ensure that

Q((100)) = [110].

Now we are left with only 6 possibilities, and it is no problem to check that, up to equivalence, we have only one crooked function:

Q((101)) = [011],
Q((110)) = [101],
Q((111)) = [111].

Let G be the corresponding crooked graph. The property (iii) from Proposition 15 is trivially satisfied; therefore, choosing any vertex of G as (0, 0, 0), we arrive at a crooked labelling. As this new labelling is equivalent to the initial one, we conclude that the automorphism group of G is vertex-transitive. □

The automorphism group turns out to be isomorphic to 2 × 2^{3}.L(3, 2), the extension being non-split ([dCMM]).

A final remark. The authors have not been able to find examples of crooked functions other than those found by de Caen et al. (described here after Proposition 11). Nevertheless, neither the conditions of Definition 1 nor those of Proposition 11 seem too restrictive. We hope that many other crooked functions (and crooked graphs) can be found.

References

[dCMM] D. de Caen, R. Mathon, G.E. Moorhouse. A Family of Antipodal Distance-Regular Graphs Related to the Classical Preparata Codes. Journal of Algebraic Combinatorics 4 (1995), 317–327.

[CvL] P.J.Cameron, J.H.van Lint. Designs, Graphs, Codes and their Links. LMS Student Texts, 22, Cambridge, 1991.

[GH] C.D. Godsil, A.D. Hensel. Distance Regular Covers of the Complete Graph. Journal of Combin. Th. Ser. B 56 (1992), 205–238.

[R] O.S. Rothaus. On “Bent” Functions, Journal of Combin. Th. Ser. A 20 (1976), 300–305.