P Chenaut

M Ménard

P Vaucher

L Lancelot

B Bideau

M Bourgin

Biomechanical analysis of the lumbar-pelvic-femoral complex during the onesided tilt test: A pilot study in triathletes

Keywords: low back injury, kinematic analysis, functional test, functional screening, range of motion

Introduction

Training for triathlon requires athletes to spend multiple hours of training in swimming, cycling and running. This training load increases the risk of injuries in lower back and the lower limb [START_REF] Gosling | Triathlon related musculoskeletal injuries: The status of injury prevention knowledge[END_REF]. Despite an abundant literature, the evaluation of the risk of low back pain remains complex as it lacks evidence-based recommendations and reliable functional test. Several functional movement tools are suggested to evaluate this risk in assessing mobility and joint stability [START_REF] Cook | Functional movement screening : the use of fundamental movements as an assessment of function -part 1[END_REF]). However, it does not specifically investigate the range of motion of low back. The one-sided tilt test (also know as "hip drop test") is an active voluntary movements used by osteopaths to analyse the one-side range of motions at the right and left side from a static position in individuals with nonspecific back pain (Chila 2010). The challenge is the clinical interpretation of this test though three-dimensional kinematic adaptations and musculoskeletal strategies of the movement performed on the test side and on the opposite side simultaneously on several regions (lumbar, pelvis, hip and knee). The aim of this pilot study was to use a musculoskeletal modelling approach to propose a functional screening approach of lumbar-pelvic-femoral complex range of motion during the one-sided tilt test.

Methods

Participants

Twenty-two well-trained and asymptomatic triathletes (age : 38,8 ± 12 ; years' experience : 8,3 ± 9 ; training hours : 10,1 ± 3, male : 19 ; female : 3) were recruited for this study after completing a consent form and a questionnaire to exclude medical pathology. All components of the study were designed by the Research Department of the Institute of Osteopathy in collaboration with the M2S lab (#2018-277) according to the principles of the Declaration of Helsinki.

Protocol

The one-sided tilt test is used to examine the range of motions of the low back when tilting the pelvis to the right and to left side. To do this, the participant had to bend his knee allowing the pelvis to tilt to the same side. The test was explained to the participants and repeated several times before the recordings (Figure 1). After a static trial, participants were instructed to perform the right and left one-sided tilt test in an alternate sequence.

Figure 1 Experimental set up

Musculoskeletal modelling

Three dimensional kinematics were obtained from a 24camera motion analysis system (Vicon, Oxford, UK). Markers data served as an input of a full musculoskeletal model, developed by [START_REF] Raabe | An investigation of jogging biomechanics using the full-body lumbar spine model: Model development and validation[END_REF], to compute lumbar and lower limb joint angles from the recommended OpenSim calculation steps [START_REF] Delp | OpenSim: Open-Source Software to Create and Analyze Dynamic Simulations of Movement[END_REF]. The model was scaled to match the participants' anthropometry using anatomical landmarks (segment lengths) and joint angles were calculated with a global optimisation-based inverse kinematics procedure. All joint angles were estimated at the peak of the right knee flexion (right hand side) and for the left knee flexion (left hand side) for standardizing the procedure.

Statistical analysis

Latent class analysis was then used to identify different classes of movement combination. Significance level was not corrected for multiple testing and was set at p < 0.05.

Results and discussion

All participants performed the test on both side. Fortyfour trials were analysed.

We observed an opposite kinematics between the pelvis (anterior tilt, ispsilateral side, controlateral rotation) and the sacro-lumbar joint (extension, contralateral side, ispsilateral rotation) (Figure 2). Based on its results, four classes of possible movement combinations were identified (from Class 1 with the lowest range of motion to Class 4 with the highest range of motion) and characterised by an increase in knee flexion. In addition, highest ranges of motion (Class 4) occurred when the ipsilateral knee was more flexed and when the controlateral knee is close to full extension (Table 1).

Table 1 Mean of all degree of freedom joint angles of each class of participants.

Knee flexion was most limited with reduced range of motion of pelvis tilt, then rotation and finally list. These patterns were different between the left and right side in 31.8% of the studied population.

Conclusions

The main finding of this pilot study is that biomechanical analysis allowed to better understand musculoskeletal strategies during the one-sided tilt test. Polyarticular functional dynamics could help understand different strategies and kinematic adaptations linked to over or under mechanical load of specific joints. In addition, this approach permitted to identify athletes with limited range of motion on lumbar-pelvic-femoral complex. The use of a musculoskeletal approach allows the possibility in future studies of accessing data that are difficult to measure (muscle lengths and joint forces). A better understanding of how anatomical structures function and interact during functional movement is fundamental to prevent low back pain and to objectify the impact of osteopathic treatment for example.

Figure 2

 2 Figure 2 Sacro-lumbar and pelvis joint angles during the one-sided tilt test (mean of all trials).

Acknowledgements

We acknowledge all participants and especially Thomas Bagory, Ilona Bieda and Victorien Grosset for our help during data acquisition.


Mathieu Ménard

A Sorel

R Boumpoutou

Hugo A Kerherve

Richard Kulpa

Benoit Bideau

H A Kerhervé

A musculoskeletal modelling approach of the assessment of the risk of hamstring injuries in professional soccer players: A pilot study

Keywords: overuse injury, muscle strain, opensim, simulation, injury prevention

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Hamstring injuries are the most common non-contact injuries in football and negatively affect team performance and club finances [START_REF] Buckthorpe | Recommendations for hamstring injury prevention in elite football: translating research into practice[END_REF]. Despite an abundant literature, the evaluation of the risk of hamstring injuries remains complex as it lacks evidence-based recommendations and reliable fieldtesting. The aetiology is commonly acknowledged as "multifactorial" and numerous potential risk factors have been proposed in the literature including muscle weakness, decreased flexibility, posture, fatigue, etc. [START_REF] Gabbe | Predictors of hamstring injury at the elite level of Australian football[END_REF]. It most commonly occurs in the Biceps Femoris long head (BFlh) and a previous history (in the last 12 months) is considered the main predictor of subsequent hamstring injury. Previous experimental research showed that kinematic analysis provides a global external insight but fails to apprehend musculoskeletal solicitations [START_REF] Thelen | Neuromusculoskeletal models provide insights into the mechanisms and rehabilitation of hamstring strains[END_REF]). On the contrary, analysis of musculoskeletal parameters (e.g. muscle length or strain rate) appears more relevant but direct measurement on the field is impossible, and only quantifiable through musculoskeletal modelling [START_REF] Delp | OpenSim: Open-Source Software to Create and Analyze Dynamic Simulations of Movement[END_REF]. The aim of this study was to investigate the risk of hamstring injury using a musculoskeletal approach during a functional test designed for this purpose.

Methods

Participants

Twelve professional elite footballers (age: 24 ± 4 years, height: 183 ± 12 cm, weight: 85 ± 12 kg) volunteered to participate in the study. Players were distributed in two groups, whether they sustained a hamstring history injury in the previous year ("Injured"; N = 5) or with no history of hamstring injury ("Control"; N = 7). Players were informed of study protocol prior to inclusion and that they could withdraw at any time without penalty. All components of the study were designed according to the principles of the Declaration of Helsinki and were approved by the Sports Science and Medical Department of the Stade Rennais Football Club (#2018-005-SRFC), and all trials were supervised by a medical doctor.

Protocol

After a 15-min standardised warm-up, participants performed a reactive agility task consisting in reaching one of four ground targets from a jumping start based on a visual cue displayed on a large screen whilst players where jumping. Players were instructed to reach a given target using the heel of their ipsilateral foot with leg stretched out, toes raised, and ipsilateral hand as close as possible to the target. Targets were located on the ground in front of them, oriented at 15° and 50° on right and left sides, and trial order was randomised. The test was considered complete when four successful trials on each target were recorded (Figure 1).

Musculoskeletal modelling

Three-dimensional kinematics were obtained from a 24camera motion analysis system (Vicon, Oxford, UK). Marker data served as input of a full musculoskeletal model, developed by [START_REF] Lai | Why are Antagonist Muscles Co-activated in My Simulation? A Musculoskeletal Model for Analysing Human Locomotor Tasks[END_REF] to estimate lumbar and lower limb joint angles from the recommended OpenSim calculation steps [START_REF] Delp | OpenSim: Open-Source Software to Create and Analyze Dynamic Simulations of Movement[END_REF]). The model was scaled to match participant's anthropometry and joint angles were calculated through a global optimisationbased inverse kinematics procedure. Maximal BFlh muscle length was estimated and normalised relative to resting length. Dependent variables used for group comparisons were normalised maximal BFlh length, BFlh stretch time from resting length to maximum length, and stretch rate calculated as the ratio between the first two dependent variables. Lower limb joint angles were estimated and compared between groups at the peak of BFlh.

Statistical analysis

Wilcoxon sum-rank test was conducted for all dependant variables. Significance level was set at p < 0.05.

Results and discussion

All participants performed the test. Four invalid trials were removed out of the 172 trials. We observed no significant difference between conditions (15° and 50°, p = 0.65). Maximal BFlh length and time to stretch were significantly greater in the control group. Stretch rate was not significantly different across groups (Table 1). Kinematics associated with these muscle parameters revealed that participants of the control group had greater maximal hip flexion and pelvis anterior tilt, and a smaller knee flexion than injured players (Table 2). This approach permitted to uncover different muscle kinematics between previously injured and non-injured players, where the decrease of BFlh stretching capacity was linked to a different strategy or a difficulty to stretch posterior muscle chain during this field test. This means that limitations in range of motion were greater and met more rapidly in previously pathological injured players compared to control players.

Although parameters in the sagittal plane were relatively constant within groups, both groups were characterised by great inter-individual variability in other planes, especially in hip internal rotation.

Conclusions

The main finding of this study is that musculoskeletal modelling allowed to analyse musculoskeletal function in greater detail than with a kinematics assessment alone. A longitudinal investigation was in progress to confirm those findings. The association between a specific field test and a musculoskeletal approach developed in this pilot study gives new preliminary insights on the impact of a previous history of hamstring injury on lower limb kinematics and BFlh muscle length and can help assisting medical practitioners, coaches, sport physicians and physiotherapists to prevent hamstring injuries.

Figure 1 :

 1 Figure 1: Overview of the experimental setup

Table 1

 1 Comparison of dependant variables between groups (mean of all conditions and all participants).

	Variables	Injured	Control	p
	Normalised	1.47 ± 0.09	1.54 ± 0.04	< 0.01
	maximal BFlh
	length
	BFlh stretch time	0.39 ± 0.10	0.48 ± 0.10	< 0.01
	(s)
	Stretch rate	1.30 ± 0.27	1.27 ± 0.25	0.45

Acknowledgements

We gratefully acknowledge thank all athletes for their enthusiastic participation.


Sophie Laplante
email: laplante@irif.fr

Reza Naserasr

Anupa Sunny
email: sunny@irif.fr

Sensitivity lower bounds from linear dependencies

Recently, using the eigenvalue techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least √ n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we show how to derive a proof of Huang's result using only linear dependency and independence of vectors associated with the vertices of the hypercube. Our approach leads to several improvements of the result. In particular we prove that in any induced subgraph of H n with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least n vertices at distance at most 2. As an application we show that for any Boolean function f , the polynomial degree of f is bounded above by s 0 (f )s 1 (f ), a strictly stronger statement which implies the sensitivity conjecture.

Introduction

Recently, Hao Huang [START_REF] Huang | Induced subgraphs of hypercubes and a proof of the sensitivity conjecture[END_REF] provided a beautiful short proof for the missing link of an important conjecture in complexity theory known as the sensitivity conjecture [START_REF] Nisan | On the degree of boolean functions as real polynomials[END_REF]. What Huang proved is the following graph theoretic statement:

Theorem 1.1 (Huang). Any induced subgraph of the n-dimensional hypercube with more than 2 n-1 vertices has at least one vertex of degree larger than or equal to √ n.

Huang's proof uses a few key facts: first of all (informally) it gives a signature to the hypercube H n to form a signed graph with exactly two eigenvalues. Then it uses a spectral argument known as the "interlace theorem" to determine the largest eigenvalue of the matrix corresponding to the induced subgraph of this signed graph, where the number of vertices is larger than half of the total number of vertices. Finally, the fact that the maximum degree of a graph must be larger than the maximum eigenvalue is used. The proof by Huang has since inspired works showing alternate proofs [START_REF] Knuth | A computational proof of Huang's degree theorem[END_REF], connections to exterior algebra [START_REF] Karasev | s theorem and the exterior algebra[END_REF], Clifford algebra [START_REF] Tao | Twisted convolution and the sensitivity conjecture[END_REF][START_REF] Mathews | The sensitivity conjecture, induced subgraphs of cubes, and clifford algebras[END_REF] and the Jordan-Wigner transformation [START_REF] Gu | Majorana fermions and the sensitivity conjecture[END_REF].

Knuth [START_REF] Knuth | A computational proof of Huang's degree theorem[END_REF] exhibited a collection of eigenvectors of this signed graph and using a basis for the eigenspace corresponding to the larger eigenvalue, provided a proof that while using linear algebra, does not use spectral arguments. The idea of using the linear dependence and a basis of the eigenspace for proving the sensitivity conjecture has been attributed to a comment by Shalev Ben-David [START_REF] Knuth | A computational proof of Huang's degree theorem[END_REF].

Mathews extended the result to weighted hypercubes [START_REF] Mathews | The sensitivity conjecture, induced subgraphs of cubes, and clifford algebras[END_REF], where all the edges corresponding to coordinate i have the same weight.

In this work, analyzing what makes this eigenvalues argument work, we present a proof which is based on linear dependency and the dimension of vector spaces. Our approach leads to stronger statements which we then use to derive applications in the study of the sensitivity of Boolean functions.

Specifically, we obtain the following new results. Let N F (x) be the set of all neighbours of a vertex x in the subgraph of the n-dimensional Boolean hypercube induced on a set of vertices F . The size of this set, which is the degree of x in this subgraph, is denoted by d F (x). Let N F 2 (x) be the set of vertices y ∈ F at distance 2 from x such there is a unique 2-path in this subgraph from each of them to x. Theorem 1.2. Given a set F of vertices of the n-dimensional Boolean hypercube with |F | ≥ 2 n-1 + 1, there exists vertices u, v in the subgraph induced on F with |u| and |v| having even and odd parity respectively such that

|N F (u)| + |N F 2 (u)| ≥ n and |N F (v)| + |N F 2 (v)| ≥ n.
Based on a notion of linear dependence which is the essence of this work, a stronger statement is given and proven as Theorem 5.1. As a corollary we obtain the following, which is also given in its stronger form as Corollary 5.2,

Corollary 1.3. Given a set F of vertices of the n-dimensional Boolean hypercube with |F | ≥ 2 n-1 + 1, there exists an edge uv such that d F (u) × d F (v) ≥ n in the induced subgraph on F .
As a corollary we have the following statement relating the degree of a function to its 0-sensitivity and 1-sensitivity (which will be defined in the next section), Theorem 1.4. For any Boolean function f we have deg

(f ) ≤ s 0 (f )s 1 (f ).
We illustrate in Section 5.3, by applying it to Chakraborty's family of Boolean functions, that this is a strictly stronger statement than deg(f ) ≤ s 2 (f ).

Preliminaries

The Boolean hypercube

The Boolean hypercube of dimension of n, denoted H n , is a graph whose vertex set V (H n ) is the set of all binary vectors (or strings) from Z n 2 . Two vertices are adjacent to each other if their binary difference is one of the elements of the standard basis, i.e. u ∼ v if u⊕v = e i for some i ∈ {1, 2, . . . , n} or equivalently, if their Hamming distance d H (u, v) is 1. On labeling the coordinates of the vectors in Z n 2 with elements of [n] = {1, 2, . . . , n}, there is a natural bijection between binary vectors of length n with subsets of [n]: a subset B of [n] is associated with the binary vector e B whose coordinate i is 1 if and only if i ∈ B. When B contains a single element i, we may write i in place of {i}. Thus e B is the natural extension of the standard basis and we use |B| to denote the size of B which also corresponds to the Hamming weight of the corresponding string.

The hypercube of dimension n is a bipartite graph. Vertices e B with an even |B| form one part of the hypercube and those with an odd |B| form the other part. The set of odd vertices of H n will be denoted by U odd n or simply U odd (when n is clear from the context) and the set of even vertices will be denoted by U even n or U even .

Binary functions and sensitivity

A binary function is any function from Z n 2 to Z 2 . It can be equivalently viewed as a 2-coloring of vertices of H n (not necessarily a proper coloring). Given a binary function f , a vector x is a said to be sensitive at coordinate i if f (x + e i ) = f (x). The sensitivity of x with respect to f is the number of coordinates at which it is sensitive. When viewed on a graph, it is the number of vertices of a color different from itself that it is adjacent to. The sensitivity of the function f , denoted s(f ), is then defined to be the maximum sensitivity over all vectors in Z n 2 with respect to f . Given a subset B of [n], a vector x is said to be B-sensitive with respect to f , if f (x + e B ) = f (x). The block sensitivity of x with respect to f is the maximum number of disjoint subsets B i of [n] such that x is B i -sensitive for each i. The block sensitivity of f is the maximum block sensitivity over all vectors in Z n 2 with respect to f . The 0-sensitivity of Boolean function f , denoted s 0 (f ), is the maximum sensitivity over binary vectors which evaluate to 0 on f . The 1-sensitivity of Boolean function f , denoted s 1 (f ), is defined similarly. Definition 2.1. A Boolean function is said to be parity-balanced if the number of even vectors that evaluate to 1 is the same as the number of odd vectors that evaluate to 1 (see Figure 1).

f -1 (1) U odd f -1 (0) U even (a) Parity-balanced function f -1 (1) U odd f -1 (0) U even (b) Not parity-balanced function

Polynomials and degree

For a vector v ∈ Z n 2 whose support is B, we define the multilinear polynomial P v : R n → R as follows:

P v = i∈B x i j∈B (1 -x j ).
The polynomial has the property that when restricted to the elements of Z n 2 , it takes the value 1 on v and 0 elsewhere. This polynomial has degree n where the coefficient of the term x 1 x 2 . . . x n is either +1 or -1 depending on the parity of v.

A polynomial p : R n → R represents a boolean function f if for all x ∈ {0, 1} n , p(x) = f (x). Every Boolean function can be represented by a multilinear polynomial P f which is the sum of polynomials P v such that f (v) = 1,

P f = v;f (v)=1 P v
We may now define the degree of a Boolean function f , denoted deg(f ), as the degree of the multilinear polynomial P f . Observe that a Boolean function f has full degree (i.e. degree n) if and only if it is not parity-balanced. This can also be found in [START_REF] Buhrman | Complexity measures and decision tree complexity: A survey[END_REF] and was attributed to Yao and Shi.

The sensitivity conjecture

The sensitivity conjecture as posed by Nisan and Szegedy [START_REF] Nisan | On the degree of boolean functions as real polynomials[END_REF] was the following problem,

Problem 3.1. For every Boolean function f, bs(f ) ≤ (s(f )) O(1)
The last piece of the proof of this conjecture was proved in 2019 by Huang [START_REF] Huang | Induced subgraphs of hypercubes and a proof of the sensitivity conjecture[END_REF]. Below, we state and review some of the works on the sensitivity conjecture leading up to this paper.

Nisan and Szegedy [START_REF] Nisan | On the degree of boolean functions as real polynomials[END_REF][START_REF] Tal | Properties and applications of boolean function composition[END_REF] established a strong connection between degree and block sensitivity of a Boolean function:

Theorem 3.2. (Nisan-Szegedy, Tal) For any Boolean function f , we have:

bs(f ) ≤ deg(f ) 2
This was proved using symmetrization and lower bounds on the degree of single-variable polynomials. An excellent exposition on the proof of this theorem and those that relate other measures of complexity of Boolean functions such as certificate complexity, decision tree complexity to block sensitivity can be found in [START_REF] Buhrman | Complexity measures and decision tree complexity: A survey[END_REF]. The theorem in its present form is due to Tal [START_REF] Tal | Properties and applications of boolean function composition[END_REF].

In 1992, Gotsman and Linial [START_REF] Gotsman | The equivalence of two problems on the cube[END_REF] showed the equivalence of the problem of showing that the polynomial degree of a function is at most some polynomial in the sensitivity of the function and the graph theoretic problem stated in Theorem 1.1.

For any Boolean function

f, s(f ) ≥ h(deg(f )).
A rough sketch of this proof is as follows: consider a monomial of the largest degree in the multilinear polynomial representing the Boolean function and discard all variables that do not appear in this monomial (i.e. set them to zero). The sensitivity of the modified function f might be smaller than that of the original function, but the polynomial degree of the function is preserved and f now has full polynomial degree. The range of f is taken to be {+1, -1} instead of {0, 1}. This function is further modified as g(x) = f (x)p(x) where p(x) = (-1) x i is the parity function.

Notice that if we consider the graph induced by the vertices in g -1 (0) (similarly for g -1 (1)), the graph degree of a vertex x in this subgraph is the sensitivity of x with respect to f . Equivalently, we can bypass g and consider the bipartite graph induced by the vertices in (f

-1 (0) ∩ U even ) ∪ (f -1 (1) ∩ U odd ), (similarly for (f -1 (1) ∩ U even ) ∪ (f -1 (0) ∩ U odd )).
Since the function f has full degree, f is not parity-balanced and without loss of generality assume |f -1 (1)∩ U odd | > |f -1 (1)∩U even |. This implies that there are more that 2 n-1 vertices in (f -1 (1)∩U odd )∪(f -1 (0)∩U even ). By proving Theorem 1.1, it was shown that the induced subgraph on this set of vertices has a vertex with sensitivity at least √ n = deg(f ). Hatami et al. [START_REF] Hatami | Variations on the Sensitivity Conjecture[END_REF] provides a clear presentation of this proof and surveys in detail the results leading up to the recent proof of the sensitivity conjecture. Putting together Theorem 1.1, Theorem 3.2 and Theorem 3.3, we now have that bs(f ) ≤ s(f ) 4 .

Graph degree lower bound revisited

In this section we first state the key tools and ideas that go into our simplification of Huang's theorem (Theorem 1.1) and then provide the details. Given a hypercube H n , let σ be an assignment of + or -to the edges such that each 4-cycle has an odd number of negative edges. As we shall see, this is the only property of Huang's signature that is needed to derive the degree lower bound. Such a signature has been introduced independently in a number of places, in many of them implicitly. For the sake of completeness, we will discuss in Section 4.1 the construction of such a signature, how to find all such signatures and we will provide some references to previous appearances of this signature. To simplify notation, we extend σ by setting it to 0 for all non-adjacent pairs of vertices in the Boolean hypercube.

A crucial step in our approach is the following definition. Recall that a binary vector or a binary string of length n is a vertex of H n . For any vertex x of H n , we define a real valued vector x + of length 2 n whose coordinates are labeled by vertices y of H n . We use x + (y) to denote the value at coordinate y of a vector x + .

Definition 4.1. For all vertices x of H n , we define the vectors x + and x -as follows, For all y ∈ V (H n ),

x + (y) = √ n if x = y σ(x, y) otherwise , x - (y) = - √ n if x = y σ(x, y) otherwise .
Note that each of the vectors x + or x -is non-zero only at the coordinates corresponding to x and its neighbors in the hypercube. We use V + and V -to denote the subspace generated by the vertices x + and x -, i.e.

V + = x + 1 , x + 2 , . . . , x + 2 n and V -= x - 1 , x - 2 , . . . , x - 2 n .
One may observe that V + and V -are the eigenspaces of the signed adjacency matrix, but we will not use this fact in our proofs.

A set of vectors S = {v 1 , v 2 , . . . , v k } is said to have a linear dependency if we have i a i v i = 0 for some choice of real numbers a i not all of which are zero, and where 0 is the all-zero vector.

Theorem 1.1 is the immediate corollary of the following facts:

Observation 4.2. If the vectors {x + 1 , x + 2 , . . . , x + k } have a linear dependency, then the subgraph induced on the corresponding vertices {x 1 , x 2 , . . . , x k } of H n has a vertex of degree at least √ n.

Proof. Suppose a i x + i = 0 with a i = 0 and let |a j | be a largest among all |a i |'s. For the row corresponding to vertex x j to vanish when viewing x + i as a column vector, there must be at least √ n other vectors in the linear dependency that are nonzero at the coordinate x j . Since those vectors can only correspond to neighbours of x j each of which can contribute at most |a j | to the sum, x j must have at least √ n neighbours.

Proposition 4.3. The subspaces V + and V -are each of dimension 2 n-1 .

A proof of this will be given in Section 4.2. As an immediate corollary we have that for any set of 2 n-1 + 1 vertices, there must be a linear dependency among some of the corresponding vectors which implies the existence of a vertex of degree at least √ n.

Signatures with negative 4-cycles

Let us first see the construction of a signature on H n such that every 4-cycle in H n is negative, i.e., the product of the signs on the edges in the cycle is negative. A signature with this property was used in [START_REF] Ahmadi | Minimum number of distinct eigenvalues of graphs[END_REF] to show that one can choose nonzero weights on the edges to have exactly two eigenvalues for the corresponding weighted graph. This is implicit in the proof of Theorem 6.7 and its Corollary 6.9 in [START_REF] Ahmadi | Minimum number of distinct eigenvalues of graphs[END_REF]. This is the same signature that was given by Huang inductively.

A signature with this property can easily be constructed on H 2 which consists of a single C 4 : assign to one or three edges a negative sign, and to the rest a positive sign. H n is built recursively from two disjoint copies of H n-1 by adding a matching between corresponding vertices. Having found a signature σ n-1 for H n-1 , proceed as follows: in the first copy of H n-1 assign signs as in σ n-1 , and in the other copy assign signs complementary to that in σ n-1 . Finally, all edges in the matching are assigned the same sign. Observe that 4-cycles in each of the two copies inherit the property. The 4-cycles formed using two edges of the matching use corresponding edges from the two copies which are of opposite signs.

We point out that there are exactly 2 2 n -1 signatures with this property on H n . Given one such signature, one can get another by a switch at a vertex x of H n , i.e. by switching the signs of edges incident on x. Observe that this operation does not change the sign of a cycle. In terms of matrices, this is equivalent to multiplying both the row and column of the adjacency matrix corresponding to x by -1. This does not change the eigenvalues and the corresponding eigenvectors are obtained by switching the sign at the x th coordinate. One may apply a series of switches on all the vertices in a set X. A series of switches on the complement of X results in the same assignment and so there are 2 2 n -1 signatures.

On the other hand any signature with the property that all 4-cycles are negative is one of the signatures discussed above. This follows from the fact that the 4-cycles generate the cycle space of H n and from the following Theorem of Zaslavsky.

Theorem 4.4 (Zaslavsky [START_REF] Zaslavsky | Signed graphs[END_REF]Theorem 3.2]). Given two signatures σ 1 and σ 2 of a graph G, σ 1 is a switching of σ 2 if and only if the sets of positive (or equivalently negative) cycles of (G, σ 1 ) and (G, σ 2 ) are the same.

Dimensions of V + and V -

Here we show that both V + and V -have dimension 2 n-1 (Proposition 4.3). We first observe that each of these subspaces have dimension at least 2 n-1 . More generally we have: Proposition 4.5. For any independent set I of vertices of H n , the sets {x + |x ∈ I} and {x -|x ∈ I} are linearly independent.

Proof. Since I is an independent set and the vector x + (resp. x -) is non-zero only at the coordinate x and its neighbors in the hypercube, x + (resp. x -) is the only vector in {y + |y ∈ I, y = x} (resp. in {y -|y ∈ I, y = x}) which is nonzero at the coordinate x.

Since the set of odd vertices (similarly even vertices) forms an independent set of size 2 n-1 in H n we have: Corollary 4.6. The dimension of vector spaces V + and V -are at least

2 n-1 , i.e. dim(V + ) ≥ 2 n-1 , dim(V -) ≥ 2 n-1 .
The fact that equality holds in each of these inequalities is a consequence of the following proposition.

Proposition 4.7. The subspaces V + and V -are orthogonal to each other.

We note that the choice of a signature where each 4-cycle is negative is key for this claim to hold.

Proof. We must show that for an arbitrary choice of vertices x and y (not necessarily distinct) the vectors x + and y -are orthogonal. Depending on the distance between x and y, we consider the following 4 cases: Case 1. If x = y, then the non-zero terms in the inner product are at the coordinate x and its neighbors.

x + , x -= - √ n • √ n + z:z∼x σ(x, z) 2 = -n + n = 0
Case 2. If x ∼ y, then the only non-zero coordinates in the inner product are x and y (since x and y do not share any common neighbours).

x

+ , y -= √ nσ(x, y) - √ nσ(x, y) = 0 Case 3. If d H (x, y) = 2
, observe that there are exactly two vertices (say v and v ) adjacent to both x and y. These form a 4-cycle and by the assumption on the signature σ, σ(x, v)σ(v, y) = -σ(x, v )σ(y, v ). Therefore,

x + , y -= σ(x, v)σ(v, y) + σ(x, v )σ(y, v ) = 0
Case 4. If d H (x, y) ≥ 3, there are no common non-zero terms in the vectors and the inner product x + , y -is trivially 0.

This completes the proof of orthogonality.

Strengthening Huang's result

Huang's proof yields a lower bound on the graph degree when the number of vertices is large enough. We can strengthen this result in two ways. First, we can weaken the hypothesis to any graph presenting a linear dependency regardless of the number of vertices in the linear dependency. Second, we can exploit the linear dependency further to extract more structural information about the graph, in addition to its largest degree.

Structural information from linear dependencies

We introduce the following terminology before going into our results. Consider a non-trivial linear relation F given as

u∈U odd a u u + = v∈U even b v v +
where a u and b v are real numbers, allowed to be 0. We are interested in cases where not all of the coefficients are 0 and in such cases F is called a nontrivial linear dependency. Let H F denote the subgraph of the Boolean hypercube induced by the vertices of H n which have a nonzero coefficient in F . By Proposition 4.3, for any set K of vertices of H n with |K| ≥ 2 n + 1 there exists a nontrivial linear dependency F such that V (H F ) ⊆ K. Thus the following theorem is stronger than the Theorem 1.2 stated in the introduction.

∈ U even in H F such that |N F (u)| + |N F 2 (u)| ≥ n and |N F (v)| + |N F 2 (v)| ≥ n.
The proof of this theorem will be given after a technical lemma. We would like to first point out a corollary of this theorem. This corollary is observed by taking a vertex u given by the theorem and considering its neighbor which has the largest degree in H F among all neighbours of u.

Corollary 5.2. If F is a nontrivial linear dependency relation, there exists an edge

(u, v) in H F such that d F (u) × d F (v) ≥ n.
We would like to point out that both Theorem 5.1 and its corollary are strictly stronger than their counterparts stated in the introduction because a linear dependency can happen in smaller sets, the smallest being of size n + 1 (see Section 6.3 for more details).

The key tool in the proof of Theorem 5.1 is Lemma 5.3 which follows. For any pair of vertices x and y at distance 2 in H n , there are exactly two paths of length 2 connecting them. When there is a unique 2-path connecting x and y in H F , we extend the signature to σ such that σF (x, y) = σ(x, z)σ(z, y) where z is the unique common neighbor of x and y in H F . Lemma 5.3. Given a linear dependency F defined by u∈U odd a u u + = v∈U even b v v + , for every vertex x ∈ H F ∩U odd and y ∈ H F ∩ U even we have

(n -d F (x))a x = z∈N F 2 (x)
σF (x, z)a z , and

(n -d F (x))b y = t∈N F 2 (x)
σF (t, y)b t .

Proof of Lemma 5.3. The vectors u + , v + are viewed as column vectors. In the linear dependency, consider the row corresponding to some arbitrary fixed coordinate x ∈ U odd .

√ na x = v∈N F (x) σ(x, v)b v (1)
Similarly by considering the row corresponding to any coordinate v ∈ U even we get:

√ nb v = u∈N F (v) σ(u, v)a u . (2)
Multiplying both sides of Equation ( 1) by √ n we have:

na x = v∈N F (x) σ(x, v) √ nb v . (3)
Replacing each √ nb v on the right side of Equation ( 3) by the corresponding right side of Equation 2, we have:

na x = v∈N F (x) u∈N F (v) σ(u, v)σ(v, u)a u . (4)
On examining the right side of this identity we make two key observations. The first is that a x appears for each v in its neighbourhood with a coefficient σ(x, v) 2 = 1. The second, which is based on the main property of the signature we have chosen to work with, is that if a vertex u, u = x, appears on the right hand side twice, then the sum of its coefficients is 0 (this is equivalent to saying

σ(x, v 1 )σ(v 1 , u) = -σ(x, v 2 )σ(v 2 , u) where x, v 1 , u, v 2 is a 4-cycle in H F ).
Rearranging the terms and simplifying gives (n

-d F (x))a x = u∈N F 2 (x)
σF (x, u)a u , as claimed. The proof of the identity for the vertices in U even is analogous.

We can now complete the proof of the statement about the second neighborhood of vertices in H F . The following, which immediately follows from Corollary 5.2, is already stronger than Theorem 1.1 because the dimension of V + is 2 n-1 . It is a strictly stronger statement because linear dependency may occur over much smaller sets of vertices.

Corollary 5.4. If F is a nontrivial linear dependency relation, then there exists a vertex u in H F such that d F (u) ≥ √ n.

From linear dependency to sensitivity

Finally, we derive a stronger upper bound on the polynomial degree of a boolean function.

Theorem 5.5. For any Boolean function f, deg(f ) ≤ s 0 (f )s 1 (f ).

Proof. If deg(f ) is d, we can concentrate on a function f of degree d on d variables by setting the variables outside of the largest monomial to 0. This can only decrease the sensitivity. Recall that Observation 4.2 states that any linear dependency among the vectors of V + corresponding to a set of vertices F implies the existence of a vertex with graph degree at least √ d. From Gotsman and Linial (see Theorem 3.3), we know that the sensitivity with respect to f of input x is the graph degree of a vertex x in the bipartite subgraph induced by F = (f -1 (0) ∩ U even ) ∪ (f -1 (1) ∩ U odd ) or F = (f -1 (1) ∩ U even ) ∪ (f -1 (0) ∩ U odd ) depending on f (x) and the parity of |x|. Since f has full polynomial degree, it is not parity-balanced. Therefore one of these bipartite subgraphs has at least 2 d-1 + 1 vertices. Since the dimension of V + is 2 d-1 , any set of 2 d-1 + 1 vectors from V + has a linear dependency and the larger of the two induced subgraphs, say F wlog, has a linear dependency. Therefore, there exists some vertex in this induced subgraph that has graph degree at least √ d. This proves that the sensitivity of the function is at least √ d = deg(f ) as d is the degree of the original function f . For the stronger statement, we use Corollary 5.2, which says that in any non-trivial linear dependency, there exists an edge (u, v) in the subgraph F such that d F (u)d F (v) ≥ d. By definition of F , f (u) = f (v), so s 0 (f )s 1 (f ) ≥ s 0 (f )s 1 (f ) ≥ d = deg(f ).

Notice that we have proven something stronger, which is that the lower bound on s 0 and s 1 is achieved on inputs at Hamming distance 1.

Since by Theorem 3.2 bs(f ) ≤ deg(f ) 2 , we get the following polynomial relation between sensitivity and block sensitivity.

Corollary 5.6. For any Boolean function f , bs(f ) ≤ s 0 (f ) 2 s 1 (f ) 2 .

Application of the degree bound

For many known functions, s 0 (f )s 1 (f ) ≥ n. It was suggested by Kenyon and Kutin [START_REF] Kenyon | Sensitivity, block sensitivity, and l-block sensitivity of boolean functions[END_REF] that for most "interesting" functions, this was the case, making it difficult to find cases where s 0 (f )s 1 (f ) gives a non-trivial upper bound on degree. One such family of functions was given by Chakraborty [START_REF] Chakraborty | Sensitivity, block sensitivity and certificate complexity of boolean functions[END_REF][START_REF] Chakraborty | On the sensitivity of cyclically-invariant Boolean functions[END_REF]. To present this family of u. We call such a linearly independent set a basic linearly independent set. The main example of a basic linearly independent set is the set {u + | u ∈ U odd } or {v + | v ∈ U even }. Each of these sets provides an orthogonal basis for the V + .

Another example of basic linearly independent set is the set of all u + where, for a fixed i, the i th coordinate of u is 1. Then for each u + of this set, the vector u + is the only vector of the set that is not 0 at the coordinate u + e i . Thus taking all such vectors provides another basis for V + , but this basis is no longer an orthogonal one. The proof of Huang's result given by Knuth in [START_REF] Knuth | A computational proof of Huang's degree theorem[END_REF] uses one such basis with i = n.

Figure 1 :

 1 Figure 1: Parity-balance in a Boolean function can be thought of as the equality of the shaded regions in the figure above. A function has full degree if and only if it is not parity-balanced.

Theorem 3 . 3 .

 33 (Gotsman-Linial) The following are equivalent for any monotone function h : N → R:1. For any induced subgraph G of H n such that |V (G)| = 2 n-1 , there exists a vertex with degree ≥ h(n) in either G or H n -G.

Theorem 5 . 1 .

 51 Given a nontrivial linear dependency relation F on a subset of vertices in H n , there exist vertices u ∈ U odd and v

Proof of Theorem 5 . 1 .

 51 Consider a (nontrivial) linear dependency u∈U odd a u u + = v∈U even b v v + and let |a x | = max z∈U odd {|a z |}. Observe that a x = 0 by our assumption on F . Now consider the identity (n -d F (x))a x = z∈N F 2 (x) σF (xz)a z . Since |a z | ≤ |a x |, there should be at least n -d F (x) values of a z which are nonzero for this identity to hold. An analogous argument follows for the other part by taking the maximum value over |b v |.

Acknowledgement

This work is supported by the ANR-France project HOSIGRA (ANR-17-CE40-0022). This project has received funding from the European Union's Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 754362.

functions we use notation from regular expressions, where a set represents alternative, juxtaposition represents concatenation, and exponents represent repetition. Definition 5.7. Given positive integer k ≥ 8 and integer n ≥ k 2 , the Chakraborty function f n,k is defined using the following auxiliary function g k : {0, 1} k 2 → {0, 1}.

where Σ = {0, 1}. The function f n,k : {0, 1} n → {0, 1} evaluates to 1 if and only if there exists a (consecutive) substring z of length k 2 such that g(z) = 1.

An alternate definition of the auxiliary function g k can be given by defining the set C k of k 2 -length strings on which g k evaluates to 1. To define C k , we first partition the k 2 coordinates into k blocks of k consecutive coordinates. A binary vector of length k 2 is in C k iff in the first block the first two positions are 1's followed by k -2 0's, in all the other blocks the starting five positions are 1's, and the last block ends with three 1's (the other positions in these blocks are unconstrained).

Chakraborty showed the following properties.

Proposition 5.8 ( [START_REF] Chakraborty | Sensitivity, block sensitivity and certificate complexity of boolean functions[END_REF][START_REF] Chakraborty | On the sensitivity of cyclically-invariant Boolean functions[END_REF]). For any k ≤ √ n,

Using Theorem 5.5, we give a new upper bound on the polynomial degree of f n,k . Proposition 5.9. For any k ≤ √ n.

The first item is immediate from Theorem 5.5 and Proposition 5.8. For the second item we use the upper bound bs(f ) ≤ deg(f ) 2 (Theorem 3.2).

Further discussion

In this section we look at some further implications of techniques developed in the previous sections. We look at how they can be used to prove analogous results in weighted hypercubes and what they imply for cases where the maximum degree of the subgraph is close to √ n.

Weighted version

Let {a i } for i = 1, 2, . . . , n be a sequence of non zero real values. Consider the following weight assignment to the edges of H n : if the edge (x, y) corresponds to the coordinate i (i.e., x and y differ only at the coordinate i), then the edge (x, y) is assigned a weight a i . Furthermore, we multiply the weight of the edge (x, y) to the signature of the edge σ(xy) which was defined in the previous sections. The adjacency matrix of the corresponding signed weighted graphs has exactly two eigenvalues: ± a 2 1 + a 2 2 + . . . + a 2 n . This would follow from Theorem 6.7 of [START_REF] Ahmadi | Minimum number of distinct eigenvalues of graphs[END_REF] if one follows the proof steps to complete the proof of Corollary 6.9 starting with K 2 . However, without the use of this fact and with a modification of our proof of Theorem 1.1, we can give a proof of the following weighted version of Huang's theorem, first proved by Mathews [START_REF] Mathews | The sensitivity conjecture, induced subgraphs of cubes, and clifford algebras[END_REF] using Clifford algebras. Theorem 6.1. Given a weighted hypercube H n where the edges corresponding to coordinate i are given a weight a i with a i = 0, in the induced subgraph corresponding to any set of 2 n-1 + 1 vertices, there exists a vertex x whose sum of weights of incident edges is at least a 2 1 + a 2 2 + . . . + a 2 n .

Proof. Once the definitions of the vectors x + and x -are modified, the rest of the proof is exactly the same. The x th coordinate of x + is set as a 2 1 + a 2 2 + . . . + a 2 n and that of x -is set as -a 2 1 + a 2 2 + . . . + a 2 n . If y is adjacent to x and y = x + e i , then the y th coordinate of both x + and x -is set as σ(xy)a i . All other coordinates are set to 0.

We note that methods of Section 5 can apply to this weighted version to get analogous stronger results.

Tightness

To summarize our result, what we have proved here is that in a subgraph induced by a set of vertices with a linear dependency, the maximum degree lies between n and √ n, with both extremities being tight. Furthermore, we proved that the closer we are to the lower bound the more vertices we must have from the second neighbourhood of a vertex with maximum degree. However this is not the limit of our approach, it can imply more vertices from the third neighbourhood and so on. While we do not yet have the strongest claim to present, we have the following observation in the case where the maximum degree is exactly √ n (assuming that n is a perfect square). Theorem 6.2. If F is a nontrivial linear dependency relation and H F has maximum degree exactly √ n, then the vertices in

This theorem is corollary of our proof of Observation 4.2 and its details is left to the reader.

The folklore example of AND-of-ORs function, defined below, exhibits such a behaviour. Let n = k 2 and B 1 , B 2 , . . . , B k be a partition of n coordinates into k blocks each of size k. The AND-of-ORs function assigns to an input x a value 1 if for each B i , x has a 1 in at least one coordinate of B i and it assigns 0 to x otherwise. We refer to [START_REF] Hatami | Variations on the Sensitivity Conjecture[END_REF] and references therein for details about this function.

Linear dependency

We remark that the vectors x + and x -were built by further investigating Huang's proof using eigenvalues. The set V + generated by {x + | x ∈ V (H n )} is the eigenspace corresponding to the eigenvalues √ n of the incidence matrix of the signed graph (H n , σ) and the set V -generated by {x -| x ∈ V (H n )} is eigenspace corresponding to the eigenvalue -√ n. This provides an alternate proof for the fact that V + is orthogonal to V -and that each is of dimension (at most) 2 n-1 .

Our approach to this problem suggests a strong connection between linear dependency of the vectors x + i in the study of the sensitivity of a function. It is, therefore, intriguing to ask: Problem 6.3. What are the (minimal) subsets of V + that are linearly dependent?

The smallest linear dependency is among a vertex and all its neighbours:

On the other hand for linearly independent sets, the easiest examples are sets I of vectors x + 's where for every vector x + ∈ I there exists a coordinate u ∈ V (H n ) such that x + is the only vector in I that is nonzero at


Janne I Kokkala

Karen Meagher

Reza Naserasr

Kari J Nurmela

Patric R J Östergård

Brett Stevens

On the Structure of Small Strength-2 Covering Arrays

A covering array CA(N ; t, k, v) of strength t is an N × k array of symbols from an alphabet of size v such that in every N × t subarray, every t-tuple occurs in at least one row. A covering array is optimal if it has the smallest possible N for given t, k, and v, and uniform if every symbol occurs N/v or N/v times in every column. Prior to this paper the only known optimal covering arrays for t = 2 were orthogonal arrays, covering arrays with v = 2 constructed from Sperner's Theorem and the Erdős-Ko-Rado Theorem, and eleven other parameter sets with v > 2 and N > v 2 . In all these cases, there is a uniform covering array with the optimal size. It has been conjectured that there exists a uniform covering array of optimal size for all parameters. In this paper a new lower bound as well as structural constraints for small uniform strength-2 covering arrays are given. Moreover, covering arrays with small parameters are studied computationally. The size of an optimal strength-2 covering array with v > 2 and N > v 2 is now known for 21 parameter sets. Our constructive results continue to support the conjecture.

Introduction

A covering array CA(N ; t, k, v) of strength t is an N × k array of symbols from an alphabet of size v such that in every N × t subarray, every t-tuple occurs in at least one row. We will use Z v = {0, 1, . . . , v -1} as the alphabet for all of our covering arrays. A covering array is optimal if it has the smallest possible N for given t, k, and v, and uniform if every symbol occurs either N/v or N/v times in every column. A uniform CA(N ; t, k, v) is denoted by UCA(N ; t, k, v). The smallest value of N for which a CA(N ; t, k, v) (respectively UCA(N ; t, k, v)) exists is denoted by CAN(t, k, v) (respectively UCAN(t, k, v)).

Covering arrays are extensively studied designs with many applications. There are several surveys of covering arrays [START_REF] Colbourn | Combinatorial aspects of covering arrays[END_REF][START_REF] Hartman | Software and hardware testing using combinatorial covering suites[END_REF][START_REF] Lawrence | A survey of binary covering arrays[END_REF]; for more recent studies see [START_REF] Akhtar | Covering arrays of strength four and software testing[END_REF][START_REF] Colbourn | Augmentation of covering arrays of strength two[END_REF][START_REF] Colbourn | Suitable permutations, binary covering arrays, and Paley matrices[END_REF][START_REF] Francetić | Asymptotic size of covering arrays: an application of entropy compression[END_REF][START_REF] Sarkar | Partial covering arrays: algorithms and asymptotics[END_REF][START_REF] Torres-Jimenez | Construction of non-isomorphic covering arrays[END_REF][START_REF] Tzanakis | Covering arrays from m-sequences and character sums[END_REF]. Uniform covering arrays are particularly useful since they are used in some constructions to create larger covering arrays [START_REF] Colbourn | Asymptotic and constructive methods for covering perfect hash families and covering arrays[END_REF][START_REF] Francetić | Asymptotic size of covering arrays: an application of entropy compression[END_REF][START_REF] Sarkar | Upper bounds on the size of covering arrays[END_REF][START_REF] Yuan | Covering array bounds using analytical techniques[END_REF]. In this work, we only consider strength-2 covering arrays; thus we omit the parameter t for brevity, and write CA(N ; k, v) and UCA(N ; k, v) instead of CA(N ; 2, k, v) and UCA(N ; 2, k, v), respectively. We also use CAN(k, v) and UCAN(k, v) for CAN (2, k, v) and UCAN (2, k, v).

A covering array with N = v 2 is an orthogonal array and it is necessarily both uniform and optimal. For v = 2 it is known ( [START_REF] Katona | Two applications (for search theory and truth functions) of Sperner type theorems[END_REF][START_REF] Kleitman | Families of k-independent sets[END_REF]) that CAN(k, 2) = n, where n -2 (n -1)/2

< k ≤ n -1 n/2 .
Moreover, for v = 2 and all k, there is a uniform covering array of optimal size, so UCAN(k, 2) = CAN(k, 2) (this is a consequence of a graph homomorphism and graph core result [START_REF] Meagher | Covering arrays on graphs[END_REF]Theorem 5]).

Prior to this work, as far as we have been able to verify, the other optimal values known when N > v 2 were CAN(5, 3) = 11, CAN(6, 3) = CAN(7, 3) = 12, CAN(8, 3) = CAN(9, 3) = 13, CAN(10, 3) = 14, CAN(6, 4) = 19, CAN(7, 4) = 21, CAN(7, 5) = 29, CAN(4, 6) = 37, and CAN [START_REF] Colbourn | Augmentation of covering arrays of strength two[END_REF][START_REF] Colbourn | Suitable permutations, binary covering arrays, and Paley matrices[END_REF] = 39 (see Table 2 in the current paper for references). In all these cases, there exists an optimal covering array that is also uniform. In fact, to date there has not been a single set of parameters found for which none of the optimal covering arrays is uniform. This has led the second and sixth author of the current paper to make the following conjecture [23, Conjecture 1].

Conjecture 1. If there exists a CA(N ; k, v) then there exists a UCA(N ; k, v).

Recently, Torres-Jimenez [42] found examples of optimal, but not uniform, covering arrays with the additional property that the array has the maximum number of columns (maximum k) for the given number of rows (given N ). One generalization of covering arrays is covering arrays avoiding forbidden edges where certain pairs of symbols in certain columns are forbidden [START_REF] Danziger | Covering arrays avoiding forbidden edges[END_REF]. There exists an arc-transitive 4-partite graph where the unique optimal covering array avoiding the edges of the graph cannot be uniform [START_REF] Stevens | Non-uniform covering array with symmetric forbidden edge constraints[END_REF]. This does not refute the conjecture but it does show that placing even highly symmetric constraints on covering arrays can force non-uniformity of optimal arrays.

An analogous problem has also been studied for covering and packing (error-correcting) codes. For binary covering codes, there are sets of parameters for which all optimal codes are nonuniform [START_REF] Östergård | Disproof of a conjecture on the existence of balanced optimal covering codes[END_REF]. For binary errorcorrecting codes, there are even sets of parameters for which all optimal codes have a nonuniform distribution of coordinate values in all coordinates [START_REF] Östergård | On optimal binary codes with unbalanced coordinates[END_REF].

The main challenge in studying Conjecture 1-in searching for a counterexample-is to determine CAN(k, v). This can be done via a lower bound and a constructive upper bound that meet. There are some well-known constructions for covering arrays. Specific covering arrays can be found by metaheuristic search techniques [START_REF] Cohen | Designing test suites for software interaction testing[END_REF][START_REF] Nurmela | Upper bounds for covering arrays by tabu search[END_REF], using constraint programming models [START_REF] Hnich | Constraint models for the covering test problem[END_REF] or by applying post-optimization techniques to known constructions [START_REF] Nayeri | Randomized post-optimization of covering arrays[END_REF]. In practice, however, strong enough bounds are in general available only for limited sets of parameters [START_REF] Hnich | Constraint models for the covering test problem[END_REF][START_REF] Stevens | Transversal Covers and Packings[END_REF] A new lower bound on the size of covering arrays is proved in this paper. Analytical methods can be augmented with computational techniques, which will be utilized in the current work to determine CAN(k, v) up to the limits set by the available algorithms and computational resources.

In this paper, new lower bounds and structural constraints on uniform covering arrays are given in Section 2. Computational methods, including exhaustive search and classification procedures, are described in Section 3. Equivalent covering arrays can be made from permuting columns, rows, or symbols. A central aspect of efficient exhaustive search in general and classification in particular is avoiding finding different copies of the same array; this process is called isomorph rejection. These concepts are discussed in more detail in Section 3. An extensive table of classification results is given in Section 3.2. Finally, our computational results are discussed in Section 4, which also contains updated tables of bounds on CAN(k, v) and UCAN(k, v) for 4 ≤ k ≤ 10 and 3 ≤ v ≤ 6.

Bounds for small covering arrays 2.1 A lower bound for uniform covering arrays

The following theorem can be used to get a lower bound on the size of a uniform covering array.

Theorem 1. Let C be a UCA(N ; k, v). Let d = N/v and i = N -vd. Then (k 2 -3k+2v)N 2 -v(k(2v-1)-2)(k-1)N +k(k(v 4 -v 3 +vi-i 2 )-(v 4 -v 3 +3vi-3i 2 )) ≥ 0
and a necessary condition for equality is that every pair of rows in C agree in at least one and at most two columns.

Proof. Let C be a UCA(N ; k, v), d = N/v , and i = N -vd. To arrive at the inequality, we will find an upper and a lower bound for the number of pairs of rows which agree in at least one position. An upper bound is the total number of pairs of rows, N 2 .

To get a lower bound on the number of pairs of rows we introduce two new parameters. Define M 1 to be the number of triples (r, r , c) for which rows r and r agree in column c. Further define M 2 to be the number of quadruples (r, r , c, c ) for which rows r and r agree in columns c and c . Then M 1 -M 2 is a lower bound on the number of pairs of rows which agree in at least one position. (Indeed, M 1 -M 2 consists of the first two terms in the summation using the principle of inclusion and exclusion.)

This gives us the bound

M 1 -M 2 ≤ N 2 , (1)
which is tight if and only if every pair of rows in C agree in at least one and at most two columns. Since the array is uniform, in every column there are i symbols which appear d + 1 times and v -i symbols which appear only d times. Thus the contribution to M 1 from any column is i d+1

2 + (v -i) d
2 and the sum of these over all columns is

M 1 = k i d + 1 2 + (v -i) d 2 = kd(N -v + i) 2 . (2)
The number of pairs of rows that agree in columns c and c is then x µ c,c x . For each x, let m c

x be the number of times x occurs in column c. Since y λ c,c

x,y = m c x and λ c,c x,y ≥ 1 for all y, it can be seen that Equation (3) is maximized for each x when there is a y x such that λ c,c

x,yx = m c x + 1 -v, and λ c,c

x,y = 1 for all y = y x . This gives

x µ c,c x ≤ x m c x + 1 -v 2 = i d + 2 -v 2 + (v -i) d + 1 -v 2 . (4)
The last equality follows from the fact that i symbols occur d + 1 times in column c, and v -i symbols occur d times in column c. This bound is attained if and only if there is a permutation π of {0, 1, . . . , v -1} such that the number of times x appears in column c equals the number of times π(x) appears in column c for each x, and λ x,y = 1 whenever y = π(x). Summing (4) over all pairs of columns gives us an upper bound for M 2 ,

M 2 = c,c x µ c,c x ≤ k(k -1)(d + 1 -v)(N -v 2 + i) 4 . (5)
Applying ( 2) and ( 5) to (1) and multiplying both sides by 4v yields the bound from the theorem. Theorem 1 is particularly useful for small k.

Corollary 2. If there exists a UCA(N ; v+2, v), then N ≥ v 2 +v-1. Further, if N = v 2 + v -1, then every pair of rows must agree in either one or two positions, and in each pair of columns there are exactly v -1 disjoint pairs of symbols that appear twice.

Similarly we can apply Theorem 1 to covering arrays with few columns.

Corollary 3. Assume that there exists a UCA(N ; v + j, v).

1. If j = 3, then N > v 2 + 3v/2 -5/2. If additionally 2 < v ≤ 11, then N > v 2 + 3v/2 -2. 2. If j = 4 then, N > v 2 + 2v -5. If additionally v ≤ 6, then N ≥ v 2 + 2v -4.
3. If j = 5, then N > v 2 + 7v/3 -13/2.

4. If j = 6, then N > v 2 + 8v/3 -21/2.

5. If j = 7, then N > v 2 + 3v -15.

In the previous corollary, there are similar improvements possible in the constant term in the lower bound on N when v is sufficiently small for j ≥ 5. We only state the improved bounds for j = 3 and 4.

The form of the bound in Theorem 1 does not let us easily identify its behaviour as a function of k, but, by losing the accuracy given by the residue of N mod v, we can obtain a weaker bound that has a more directly computable form.

Corollary 4. Let b = (2v -3)k 2 + (-2v + 5)k + (-4v + 2), a = 2k 2 -6k + 4v, and D = k 4 + (8v 2 -16v + 2)k 3 + (-8v 3 + 24v -3)k 2 + (8v 3 -8v 2 -8v -4)k + 4.
If there exists a UCA(N ; k, v), then

N ≥ v b + √ D a (6)
Proof. Consider a uniform covering array CA(N ; k, v). Let N be the least multiple of v that is at least N . This means that N ≤ N + v -1 and the uniform CA(N ; k, v) can be extended to a CA(N ; k, v) in which each column has each symbol occurring exactly N /k times. Theorem 1 can be applied to the CA(N ; k, v), to get that

2vN (N -1) ≥ k 2(N )(N -v) -(k -1)(N -v 2 + v)(N -v 2 ) .
This reduces to

0 ≤ (k 2 -3k + 2v)(N ) 2 -v(k -1)(2kv -k -2)N -k(k -1)(v 4 -v 3 ) ≤ 0
Then N must be bounded below by the quadratic's larger root. The result follows since N -(v -1) ≤ N .

By taking the derivative of Inequality ( 6) with respect to k and approximating its roots we compute that this bound reaches it maximum at a value of k less than, but close to

k max ≈ 16v 2 -20v -15 8v -16 = 2v + 3 2 + 9 8v -16 .
The error in this approximation is less then 0.5 after v = 16. The value of the bound at this maximum point is approximately

N v = UCAN(2, k max , v) ≥ 2.4142v -1.17678 - 3.5026v + 10.2260 8v 2 + 8v -4 .
That is, for k > k max the value of the bound from Corollary 4 is smaller than

N v . Since we know that UCAN(2, k + 1, v) ≥ UCAN(2, k, v
), the bound from Corollary 4 loses its utility for any k > k max . The maximum useful k for the bound of Theorem 1 must also be close to this k max . In our classification results six uniform covering arrays meet the bound from Theorem 1. Five have k = v + 2 and one, UCA (21; 7, 4), has k = v + 3.

Constraints on covering arrays with v + 2 columns

The strongest structural conditions implied by equality in Theorem 1 happen when k = v + 2 and N = v 2 + v -1. We further investigate covering arrays with these parameters. First we introduce some notation. In a uniform covering array UCA(v 2 + v -1; k, v), in each column every symbol occurs either v times or v + 1 times. An entry in a UCA(N ; k, v) is called a high frequency entry if the symbol in the entry occurs at least v + 1 times in the entry's column.

Theorem 5. Let C be a UCA(v 2 + v -1; v + 2, v)
and let a i be the number of rows that contain exactly i high frequency entries. Then

v+2 i=0 a i = v 2 + v -1, (7)
v+2 i=0 ia i = (v + 2)(v -1)(v + 1), ( 8
) v+2 i=0 i 2 a i = (v + 2)(v + 1) 2 (v -1). ( 9
)
Further, a 0 ≤ 1, and a 1 = a 2 = 0.

Proof. Let C be a UCA(v 2 + v -1; v + 2, v).
For a column, c, denote by S c the set of symbols in high frequency entries. We know

|S c | = v -1.
Equation ( 7) is established by simply counting the rows of C. Equation ( 8) is established by computing the cardinality of the set

{(x, c, r) | 0 ≤ c < v + 2, C r,c = x ∈ S c }.
Equation ( 9) is established by computing the cardinality of the set

{(x, c, y, c , r) | 0 ≤ c = c < v + 2, C r,c = x ∈ S c , C r,c = y ∈ S c }.
There is exactly one symbol per column that is repeated exactly v times. So if two rows had no high frequency entries, then both rows would only contain the symbols that occur exactly v times. This would mean that a pair of such symbols is repeated and C could not be a covering array. Thus a 0 ≤ 1.

To establish that a 1 = a 2 = 0, let r be a fixed row containing i symbols which appear v + 1 times in their column. For any of the other v 2 + v -2 rows b, let µ r,b be the number of columns where rows r and b agree. Counting the flags (c, b) with 0

≤ c < v + 2, b = r and C b,c = C r,c we have b =r µ r,b = v 2 + v -2 + i, (10)
µ = v 2 + v -2 + i v 2 + v -2 . ( 11
)
Counting the flags (c, c , b) such that 0

≤ c = c < v + 2, C b,c = C r,c
, and

C b,c = C r,c we have b =r µ r,b 2 ≤ i 2 , (12)
(this follows since only high frequency entries can occur twice). Using Equation [START_REF] Francetić | Asymptotic size of covering arrays: an application of entropy compression[END_REF], this implies that

b =r µ 2 r,b ≤ v 2 + v -2 + i 2 . ( 13
)
Now we get

0 ≤ b =r (µ r,b -µ) 2 = -µ 2 (v 2 + v -2) + b =r µ 2 r,b ≤ i i(v 2 + v -3) -(2v 2 + 2v -4) v 2 + v -2 . Which implies that i = 0 or i ≥ 2 + 2/(v 2 + v -3) = 3. Corollary 6. Let C be a UCA(v 2 + v -1; v + 2, v)
and let a i be the number of rows that have exactly i high frequency entries. If a 0 = 1, then a v+1 = v 2 + v -2 and a i = 0 for all other i.

Proof. If a 0 = 1 then ( 7), ( 8) and (9) imply that the average

i is i = v + 1.
The variance in the distribution of i = 0 is equal to 0, since

v+2 i=1 (i -i) 2 = -i 2 (v + 2)(v -1) + v+2 i=1 i 2 a i = (v + 2)(v -1)(v + 1) 2 -(v + 2)(v -1)(v + 1) 2 .
All this leaves open the possible existence of a CA(N ; v + 2, v) with N < v 2 + v -1 (and thus smaller than those described in Corollary 3) if only the covering array is not uniform. However some constraints exist even in this case for CA(N ; v + 2, v). In [START_REF] Stevens | Transversal Covers and Packings[END_REF], the following result is proved using a similar counting method.

Theorem 7. Assume that there exists a CA(N ; k, v) that has a row that contains at most two high frequency entries.

If k = v +2, then N ≥ v 2 +v -1; and if k ≥ v + 3, then N ≥ v 2 + v.
Assume that there exists a CA(N ; k, v) that has a row that contains at most three high frequency entries.

If k ≥ v + 2, then N ≥ v 2 + v -1.

Classifying covering arrays

In all of our computer-aided studies of covering arrays, we fix the parameters of the array: the order, v; the degree, k; and the size, N . We further consider covering arrays as multisets of their rows. (Given two multisets, S and T , the multiset sum S T is the set for which the multiplicity of each element is the sum of its multiplicities in S and T .) Two covering arrays are then said to be equivalent if one can be obtained from the other by a permutation of the columns and by column-wise permutations of the elements of Z v . A transformation that maps a covering array C onto itself is an automorphism, and the set of all automorphisms form the (full) automorphism group of C, denoted by Aut(C). Our computer search builds all inequivalent covering arrays with a given parameter set.

For isomorph rejection, we represent covering arrays as colored graphs (this is described below) and, using nauty [START_REF] Mckay | Practical graph isomorphism, II[END_REF], we may also determine the automorphism group for graphs and thereby the corresponding arrays. The colored graph G corresponding to a covering array C is constructed in the following standard way [START_REF] Östergård | Optimal binary one-error-correcting codes of length 10 have 72 codewords[END_REF].

The vertices of G will be colored with two colors. Colourings of graphs are the mechanism that nauty [START_REF] Mckay | Practical graph isomorphism, II[END_REF] uses to forbid certain mappings between vertices; they need not be proper colourings. First, G contains k disjoint copies of the complete graph of order v; all of these vertices are colored with the first color. These vertices represent the entries in the columns of the CA; the ith copy of the complete graph corresponds to the ith column and the jth vertex in each copy corresponds to the symbol j in that column. Further, G contains N vertices, representing the rows of C, all colored with the second color. Each such vertex is connected to the k vertices corresponding to the column-symbol pairs that occur in that row. Note that the obvious homomorphism Aut(G) → Aut(C) has a nontrivial kernel if there are duplicate rows.

Our main method, presented in Section 3.1, constructs one representative from each equivalence class of covering arrays, CA(N ; k, v). This is done by starting with a set of representatives of the equivalence classes of covering arrays CA(N ; 2, v), and sequentially adding columns, rejecting equivalent covering arrays after every step. Canonical augmentation [14, Sect. 4.2.3], [START_REF] Mckay | Isomorph-free exhaustive generation[END_REF] is used when extending representatives of covering arrays CA(N ; k , v) to representatives of covering arrays CA(N ; k + 1, v); this part is described in detail in Section 3.1.2. Further, since our goal is to classify all CA(N ; k, v) for certain k but not necessarily those that have a smaller number of columns, we can occasionally speed up the search by rejecting some partial arrays that cannot be extended to a full k-column covering array; the method is described in Section 3.1.3. When studying only uniform covering arrays, it is easy to modify the algorithm to require uniformity.

Algorithm

In this section, we describe the algorithm for classifying all covering arrays CA(N ; k + 1, v), starting from a set of equivalence class representatives of covering arrays CA(N ; k, v). To apply such an algorithm, we need a base case, which here is a classification of the covering arrays CA(N ; 2, v). Since all v 2 pairs of symbols must occur in the two columns of those covering arrays, we may focus on the N -v 2 excess rows and just the equivalence issue. For the excess part in the first column, the symbol distributions are in one-to-one correspondence to the integer partitions of N -v 2 into at most v parts. In the second column we may take obvious symmetries into account to reduce the number of candidates considered. Finally, equivalent arrays are rejected.

Extending covering arrays

Consider a covering array C obtained by adding a column to a covering array C. The symbols in the new column in C induce a partition of the rows of C into covering arrays of strength 1. We call a subset of C that is a covering array of strength 1 a cover of C. If no proper subset of a cover of C is a cover of C, we call it a minimal cover of C. Each cover of C has one or more subsets that are minimal covers. For a cover D, we denote the lexicographically smallest subset that is a minimal cover by φ(D).

When extending covering arrays, we first determine D, the set of all minimal covers of C. Then we find all sets {D 1 , D 2 , . . . , D v } of v minimal covers that pack inside C, that is, i D i ⊆ C. For each such set, we generate all full partitions {C 1 , C 2 , . . . , C v } of C, where D i ⊆ C i for all i, by adding the remaining rows in the sets D i in all possible ways. To avoid repetition, we reject in the search all partitions for which D i = φ(C i ). To get a covering array from an unlabeled partition, we map the symbols to the parts such that the resulting covering array is lexicographically smallest; this mapping from partitions to covering arrays is required in the sequel.

Isomorph rejection

Having generated all extensions of C up to permutation of symbols in the last column, canonical augmentation is used for isomorph rejection in two phases. The first phase rejects some arrays and ensures that two remaining arrays can be equivalent only if they were generated from the same C, and further that there is an automorphism of C that maps one onto another. The second phase then accepts precisely one array from each equivalence class. Actually the two phases can be carried out in arbitrary order, and in our implementation Condition 3 below is checked first to help in validating the results, to be discussed later.

In the first phase, we use the v-tuple consisting of the counts of each symbol in that column sorted in descending order as an invariant of a column. For example, if a column contains three entries equal to 0, six entries equal to 1, and three entries equal to 2, then the invariant is [START_REF] Colbourn | Suitable permutations, binary covering arrays, and Paley matrices[END_REF][START_REF] Cohen | Designing test suites for software interaction testing[END_REF][START_REF] Cohen | Designing test suites for software interaction testing[END_REF]. A covering array C passes the first phase of canonical augmentation if:

1. no other column has lexicographically smaller invariant than the last column, and 2. out of those columns with the same invariant as the last column, the last column is in the orbit that gets the smallest label in a canonical labeling by nauty.

Let µ be the largest multiplicity of a symbol in the column of C that has the smallest invariant. The first condition ensures that in a canonically augmented C , there is no symbol in the new column with multiplicity larger than µ. This allows us to remove from D all minimal covers with size larger than µ before the search begins and also not consider full partitions of C for which one part has size larger than µ. Condition 3 allows us to reject from D all minimal covers D that contain c for which there is a g ∈ Aut(C) such that c ∈ gD and gD < D. To this end, the row c is selected to be the one that maximizes the number of minimal covers that are rejected from D.

A pruning condition

Let N and v be integers with N < v(v + 1). Let C be a CA(N ; k, v) and let C be a CA(N ; k , v) that is obtained by adding δ = k -k columns to C.

Since N is strictly less than v 2 + v, each of the last δ columns of C contain at least one symbol of multiplicity v, each of which corresponds to a cover of size v in C. For each pair of columns and each symbol of multiplicity v, the two covers intersect in exactly one row (considering duplicate rows as separate elements). Thus C has a set of δ covers of size v which pairwise intersect in only one row.

If we are interested only in covering arrays CA(N ; k , v) and not in covering arrays CA(N ; k , v) for any k < k < k , we can restrict our search to the covering arrays CA(N ; k, v) that satisfy this property. We gain further speedup by running the search for each possible way to fix the set of δ covers of size v that intersect in the desired way, as fixing the set allows rejecting many covers in D immediately.

Some implementation details

A core subroutine of the algorithm is that of finding subsets of D that pack inside C. This was implemented in two different ways, one using Cliquer [START_REF] Niskanen | Cliquer User's Guide[END_REF] and one using libexact [START_REF] Kaski | libexact user's guide, Version 1.0[END_REF]. The simpler approach using Cliquer is faster in some cases, but in most cases, the approach using libexact is faster.

To use Cliquer we define G to be a graph with a vertex for every cover in D and an edge between two covers if their multiset sum is a subset of C. A packing corresponds to a clique of size v in G, but a clique may not be a valid packing if there are not enough duplicate rows in C. Further, when N ≥ v(v + 1), two covers in a packing may be identical, so elements in D for which all rows have multiplicity greater than 1 in C must be represented with duplicated vertices in G.

The library libexact is used to find all solutions to a system of linear equations Ax = b with 0 ≤ x j ≤ u j where A is a (0, 1)-matrix. We set up the instance as follows. For each cover in D, we have a variable whose value is the multiplicity of the cover in the packing. For each different row in C, we then have an inequality; namely, the row should occur in the packing at most as many times as it occurs in C. To encode this as an equality, we add a variable for each row that whose value is the slack in that inequality (that is, how many instances of the row in C are not covered by the packing). Further, to force a solution to have exactly v covers, we add a condition that the sum of variables corresponding to covers in D must be equal to v. The upper bounds of each variable are directly obtained from the equalities, as all variables are nonnegative.

We introduce further slack variables to account for conditions on the sizes of covers in the packing. These slack variables have no effect on the solutions but they speed up the search by identifying some branches that cannot lead to a solution. For a valid packing, let M v be the number of covers of size v, let M v+1 be the number of covers of size v + 1, and let M ≥v+2 be the number of covers of size at least v + 2. We have

M v ≤ v, ( 14
) vM v + (v + 1)M v+1 + (v + 2)M ≥v+2 ≤ N. ( 15
)
Here ( 15) is obtained by counting the rows in each cover. We define s 1 and s 2 to be the slack variables in ( 14) and ( 15), respectively, giving

s 1 + M v = v, (16)
s 1 + s 2 + M ≥v+2 = N -v 2 , ( 17
)
where we used M v + M v+1 + M ≥v+2 = v to get [START_REF] Kleitman | Families of k-independent sets[END_REF]. These equations can be directly implemented by writing M v and M ≥v+2 as sums of the variables corresponding to covers of size v or at least v + 2, respectively. The upper bound of s 1 and s 2 in the libexact instance is set to N -v 2 , which follows from (17).

Computational results

A classification is here carried out for v = 3, 4, 5, 6 and values of N up to the computational limit. The listed times refer to a single logical core of an Intel Xeon E5 family processor with multi-threading enabled. Specifically, CA(N ; k, v) are classified for 10 ≤ N ≤ 14 when v = 3, for 17 ≤ N ≤ 20 when v = 4, for 26 ≤ N ≤ 29 when v = 5, and for 37 ≤ N ≤ 40 when v = 6. The full classification is performed for all possible values of k, except for the cases of CA(29; k, 5) and CA (40; k, 6), where some values of k were skipped using the method described in Section 3.1.3 to get to the cases of CA(29; 7, 5) and CA (40; 6, 6); the latter has 0 solutions so a CA(40; k, 6) exists exactly when k ≤ 5.

Due to the computational time, we are unable to carry out a complete classification in the following cases: CA(21; k, 4) with k ∈ {3, . . . , 8}; CA(30; k, 5) with k ∈ {3, . . . , 8}; and CA(41; k, 6) with k ∈ {3, . . . , 7}. For example, we predict that classifying CA [START_REF] Mckay | Isomorph-free exhaustive generation[END_REF][START_REF] Colbourn | Covering and radius-covering arrays: constructions and classification[END_REF][START_REF] Colbourn | Combinatorial aspects of covering arrays[END_REF] would take 130 core-years.

In all these cases, the number of uniform arrays is also obtained. Finally, in the uniform cases, the classification of UCA(21; k, 4) and UCA(30; k, 5) is performed exhaustively and for UCA(41; k, 6) partially, skipping levels to get to UCA (41; 7, 6); the latter has 0 solutions so a UCA(41; k, 6) exists exactly when k ≤ 6.

A complete table of results obtained for CA(N ; k, v) and UCA(N ; k, v) is given in Table 1. When δ is not given, all covering arrays and uniform covering arrays are classified. When δ is given, the stated quantities are the numbers of covering arrays or uniform covering arrays obtained using the method in Section 3.1.3 with the given δ. These quantities are lower bounds for the numbers of all covering arrays and uniform covering arrays. In cases where the count of all covering arrays is not given, only uniform covering arrays are classified. Cliquer is used in the cases marked with †, and libexact is used in all other cases.

Because a covering array occurs as a subset of a covering array with more rows, the classification results of smaller N could be obtained from the results of larger N ; however, the running times are reported separately to give an idea of how the running time of the algorithm depends on N . The method to generate inequivalent 2-column arrays is not optimized and the time is not comparable to the other times so the time for k = 2 is not reported; in all cases the generation takes less than 10 seconds.

Double counting

To increase confidence in the computational results, we perform a consistency check of the results by double counting. After the search starting from CA(N ; k, v) is performed, we count in two ways the total number of CA(N ; k + 1, v) that obey the restrictions used, that is, in some cases we count only uniform arrays and in some cases only arrays that have δ covers of size v that intersect pairwise in exactly one row. The first way is to use the classification results to and the orbit-stabilizer theorem to obtain

C (k + 1)!v! k+1 |Aut(C )| ,
where (k + 1)!v! k+1 is the order of the group of symmetries in that case and the sum is taken over equivalence class representatives C of that case.

The second way is to use numbers that were stored during the search.

Consider first a modified search that starts from all k-column arrays instead of equivalence class representatives and considers all possible permutations of symbols in the last column for each partition. If the techniques for rejecting candidates of D in Section 3.1.2 would not be used, then every (k +1)-column covering array would appear exactly once when adding one more column.

If the additional condition on the largest multiplicity of a symbol in the last column is taken into account, then the proportion of (k+1)-column arrays equivalent to C that enter the isomorph rejection phase is the proportion of columns in C for which the largest multiplicity of a symbol is smallest, denoted by α(C ). Further, in the search starting from a fixed k-column array C, let β(C, C ) be the proportion of all partitions equivalent to C that pass the check 3 in Section 3.1.2; this can be obtained at the stage in the search when all partitions of C equivalent to C are considered. The total count of (k + 1)-column arrays would now be

C,C 1 α(C )β(C, C ) ,
where the sum is taken over all k-column arrays C and all C that are extensions of C and pass the check for Condition 3. The remaining techniques for rejecting covers in D described in Section 3.1.2 do not reject any candidates that satisfy Condition 3, so including them in the search does not change this count.

In the modified search, arrays C which differ only by a permutation of symbols in the last column contribute the same amount in the sum, and the searches starting from two equivalent C contribute the same amount to the sum. Let S(C ) be the number of ways to assign the symbols to the last column (this equals v! if no two parts in the corresponding partition of C are equal). Further, the size of the equivalence class of

C is k!v! k /|Aut(C)|.
In the actual search, the count is then obtained as

C,C k!v! k |Aut(C)| S(C ) 1 α(C )β(C, C ) ,
where the sum is taken over the k-column arrays C that are used in the search, and all C that are extensions of C and pass the check for Condition 3.

Discussion of results

A summary of the current knowledge of the sizes of optimal coverings array for small k and v is given in Table 2. In the table there are captions for Rouse-Lamarre, reported in [START_REF] Colbourn | Covering and radius-covering arrays: constructions and classification[END_REF], f) [START_REF] Lobb | Cover starters for covering arrays of strength two[END_REF], g) [START_REF] Meagher | Group construction of covering arrays[END_REF], h) [START_REF] Nurmela | Upper bounds for covering arrays by tabu search[END_REF], i) [START_REF] Östergård | Constructions of mixed covering codes[END_REF], j) Applegate, reported in [START_REF] Sloane | Covering arrays and intersecting codes[END_REF], k) [START_REF] Stevens | New recursive methods for transversal covers[END_REF], l) [START_REF] Stevens | Lower bounds for transversal covers[END_REF], m) [START_REF] Tarry | Le Problèm des 36 Officiers[END_REF], n) [START_REF] Izquierdo-Marquez | New upper bounds for pairwise senary test-suites[END_REF] Table 2: Values of CAN(k, v) for 4 ≤ k ≤ 10 and 3 ≤ v ≤ 6 all bounds, except those that follow from orthogonal arrays: CAN(k, v) = v 2 when v is a prime power and k ≤ v + 1. Some of the lower bounds attributed to the current work were obtained about two decades before this paper appears in print. Those bounds, which were announced at a conference in 2000 [START_REF] Nurmela | Lower bounds on 2-covering arrays by exhaustive search[END_REF], are given a caption of their own to clarify priority issues. Some of those results have later been rediscovered [2,[START_REF] Colbourn | Covering and radius-covering arrays: constructions and classification[END_REF]42,[START_REF] Torres-Jimenez | Construction of non-isomorphic covering arrays[END_REF]. Additionally our computer search established that a CA(14; 11, 3) does not exist. The fourth author found a CA (15; 20, 3) [27] so we additionally know that CAN(k, 3) = 15 for 11 ≤ k ≤ 20.

In the process of preparing this paper we noticed that the bound sources listed in Table 2 of [START_REF] Nurmela | Upper bounds for covering arrays by tabu search[END_REF] are not the same as those in Table 1 but this difference is not articulated in that article. To the best of our knowledge in Table 2 of [START_REF] Nurmela | Upper bounds for covering arrays by tabu search[END_REF], b refers to [START_REF] Stevens | Transversal Covers and Packings[END_REF], c is [START_REF] Nurmela | Upper bounds for covering arrays by tabu search[END_REF] and d is [START_REF] Stevens | A direct construction of transversal covers using group divisible designs[END_REF]. On page 149 of [START_REF] Nurmela | Upper bounds for covering arrays by tabu search[END_REF], "giving the bounds marked with d in the tables" should read "giving the bounds marked with b in Table 1 and c in Table 2".

In every case in which we determined the size of an optimal covering array by construction, we also determined that there exists a uniform covering array of the same size. These results continue to support the conjecture that optimal covering arrays can be found amongst the uniform covering arrays.

For the parameters CA(11; 5, 3), CA(12; 7, 3), CA(13; 8, 3), CA(13; 9, 3), CA (19; 6, 4), and CA(37; 4, 6) every optimal array is also uniform. However for the optimal parameters, CA(12; 6, 3), CA(14; 10, 3), CA(29; 7, 5), and CA(39; 5, 6) both uniform and non-uniform examples exist. Finally, for the optimal parameters CA(21; 7, 4) and CA(41; 6, 6) we know that uniform arrays exist, but we do not know if non-uniform examples also exist.

For the four optimal parameter sets where both uniform and non-uniform arrays exist, CA(12; 6, 3), CA(14; 10, 3), CA(29; 7, 5), and CA(39; 5, 6), the Combined with the optimal parameter sets where every array is uniform we can see some provisional trends. The smallest optimal parameter set for which non-uniform arrays exist is CA(12; 6, 3), for which N is the smallest for the given k, but k is not the maximal possible given N . We guess that non-uniform arrays will be more abundant when k is not maximal for a given N . The second potential trend is that for a fixed v, as N and k increase there are likely to be more non-uniform optimal arrays. These are only limited observations from few data. Table 3 shows the current state of knowledge for uniform covering arrays. All entries are lower bounds, bold entries show arrays known to exist, and underlined entries indicate a lower bound matching Theorem 1. The lower bounds from Theorem 1 meet six known uniform covering arrays.

v k = 4 k = 5 k = 6 k = 7 k = 8 k = 9 k = 10 3 9
A lower bound in Table 2 that is smaller than the corresponding lower bound in Table 3 indicates a candidate for a covering array that would refute Conjecture 1.

Conjecture 1 and Corollary 2 would imply that CAN(v +2, v) ≥ v 2 +v -1, which has also been conjectured in [START_REF] Stevens | Transversal Covers and Packings[END_REF]. When v is a prime power, this would mean that CAN(v + 2, v) -CAN(v + 1, v) ≥ v -1, which is a very large jump for only adding a single column. In the case of v = 6, from Table 2 we can see that the value of CAN(v +1, v) may be close to the value of CAN(v +2, v) when v is not a prime power.

One exciting possibility is that CAN(8, 6) could be 41, meeting the bound from Theorem 1; CAN [START_REF] Colbourn | Asymptotic and constructive methods for covering perfect hash families and covering arrays[END_REF][START_REF] Colbourn | Suitable permutations, binary covering arrays, and Paley matrices[END_REF] is no more than 42. This suggests that the influence of the prime power status of v disappears very rapidly as k increases past v + 1. However, none of the UCA (41; 6, 6) covering arrays can be extended to a CA (41; 8, 6), so if they exist, then no subarray with six columns can be uniform. This implies that at least three columns of a possible CA (41; 8, 6) must be non-uniform. Since there are six non-uniform partitions of 41 into six parts of size at least 6 there are 57 different partition patterns if only three columns are non-uniform. If more columns are non-uniform, the number of cases increases. This indicates that exploiting this structure in an exhaustive search may not be efficient. Exploiting it with a metaheuristic search could be an option.

Conjecture 1 predicts that for every covering array, there a uniform covering array with the same parameters. We have seen examples of optimal covering arrays which are not uniform, so we know that not every optimal covering array is uniform. But we can ask for which parameters are all the optimal covering arrays uniform? In this paper we found many examples, but our examples are in cases where the number of rows is relatively small. When v is a prime power it is possible to construct a CA(v 2 + i(v 2 -v i (v + 1), v) for any i using a recursive construction and starting with an orthogonal array (see, for example, [START_REF] Stevens | Transversal Covers and Packings[END_REF]). We suspect that these parameters could be good candidates for having every optimal covering arrays be a uniform covering array.

A significant result from our work is that the number of known optimal covering arrays for v > 2 and N > v 2 is now 21 whereas before it was eleven. Additionally the UCA(21; 7, 4) meet the bound from Theorem 1. This is the first example of tightness and the implied structure, when k > v + 2. The classification results from our searches are available at [START_REF] Kokkala | Dataset for On the structure of small strength-2 covering arrays[END_REF].

In this paper we only consider strength-2 covering arrays. Many of the questions addressed in the paper may be interesting for higher strength covering arrays. The definition of "uniform" applies to covering arrays of any size and it is interesting to ask if it is always possible to find an optimal covering array, of any strength, that is also uniform. Extending Theorem 1 to strength t would require counting pairs of rows which agree in at most t -1 positions and would be an interesting investigation. For strength t > 2, extending an array with an additional column requires determining all of the strength t-1 subarrays which is more computationally demanding as t increase. The use of nauty to compute automorphism groups depends mainly on the sizes of the arrays and is not inherently more complicated as the strength increases. For classification and fully understanding the structure of optimal arrays, we do not see better options than exhaustive search.

Next, we find an upper bound for M 2 .

 2 Consider columns c and c . Let λ c,c x,y be the number of rows r such that C r,c = x and C r,c = y, and let µ c,c x be the number of pairs of rows r and r such that C r,c = C r ,c = x and C r,c = C r ,c . It follows from the definition that µ

  For the second phase, we treat the array C as a partition of C. Let c be an arbitrarily chosen row of C which has multiplicity 1 and is held fixed for the search of extensions of C. Let C be the orbit of C under the action of Aut(C), and let χ(C , c) = φ(A) where A is the part in C that contains c. An array C passes the second phase if 3. χ(C , c) ≤ χ(C , c) for all C ∈ C, and 4. C is the smallest in the set {C ∈ C : χ(C , c) = χ(C , c)}, in terms of lexicographical ordering of the corresponding arrays.

v k = 4 k = 5 k = 6 k = 7 l 29 k b 30 -

 730 33 h c 30-35 h c 30-36 e 6 m 37 k a 39 d b 41 h c 41-42 c c 41-42 h c 41-46 g c 41-48 n Unmarked entries: orthogonal arrays. Captions: a) This paper, preliminarily announced in [28], b) This paper, c) CAN(k, v) ≤ CAN(k + 1, v), d) [3], e) L.

Table 1 :

 1 Detailed computational results

	v N	k δ	# CA	# UCA CPU time
	3 10 2	1	1
	3 10 3	3	3	< 0.01 s
	3 10 4	2	2	< 0.01 s
	3 10 5	0	0	< 0.01 s
	3 11 2	3	1
	3 11 3	20	9	0.01 s
	3 11 4	27	8	0.02 s
	3 11 5	3	3	0.01 s
	3 11 6	0	0	< 0.01 s
	3 12 2	7	1
	3 12 3	134	9	0.02 s
	3 12 4	987	53	0.16 s
	3 12 5	891	125	0.38 s
	3 12 6	13	11	0.10 s
	3 12 7	1	1	< 0.01 s
	3 12 8	0	0	< 0.01 s
	3 13 2	16	3
	3 13 3	937	151	0.09 s
	3 13 4	53 523	12 747	6.0 s
	3 13 5	739 845	302 524	144.5 s
	3 13 6	752 165	506 680	940.8 s
	3 13 7	24 934	22 539	600.9 s
	3 13 8	5	5	11.4 s

Table 1 :

 1 Detailed computational results (cont.)

	v N	k δ	# CA	# UCA CPU time
	3 13 9	4	4	< 0.01 s
	3 13 10	0	0	< 0.01 s
	3 14 2	32	4
	3 14 3	5 973	476	0.51 s
	3 14 4	2 212 568	214 630	580.2 s
	3 14 5	325 046 812	43 473 308	29.9 h
	3 14 6	7 759 008 032 1 516 020 148	54.1 d
	3 14 7	18 844 482 204 5 827 703 442	446.8 d
	3 14 8	2 790 300 754 1 429 724 866	519.7 d
	3 14 9	17 068 936	12 725 845	43.4 d
	3 14 10	4 490	4 117	4.1 h
	3 14 11	0	0	3.3 s
	4 17 2	1	1
	4 17 3	6	6	0.03 s
	4 17 4	3	3	< 0.01 s
	4 17 5	4	4	< 0.01 s
	4 17 6	0	0	< 0.01 s
	4 18 2	3	1
	4 18 3	79	42	0.08 s
	4 18 4	79	31	0.13 s
	4 18 5	201	67	0.08 s
	4 18 6	0	0	0.04 s
	4 19 2	7	1
	4 19 3	1 365	191	0.51 s
	4 19 4	12 368	1 995	4.7 s
	4 19 5	74 113	1 495	16.1 s
	4 19 6	4	4	20.1 s
	4 19 7	0	0	< 0.01 s
	4 20 2	21	1
	4 20 3	30 334	183	16.0 s
	4 20 4	6 409 721	65 517	2265.4 s
	4 20 5	57 544 941	214 717	12.1 h
	4 20 6	25 760	745	32.6 h
	4 20 7	0	0
	4 21 2	47	3
	4 21 3		25 763	12.1 s †
	4 21 4		246 546 229	21.7 h †
	4 21 5		19 419 386 435	228.0 d †

Table 1 :

 1 Detailed computational results (cont.)

	v N	k δ	# CA	# UCA CPU time
	4 21 6		3 100 200 221	2326.4 d †
	4 21 7		1 005	135.4 d †
	4 21 8		0	2.9 s †
	5 26 2	1	1
	5 26 3	15	15	0.87 s
	5 26 4	3	3	0.07 s
	5 26 5	6	6	< 0.01 s
	5 26 6	6	6	0.01 s
	5 26 7	0	0	< 0.01 s
	5 27 2	3	1
	5 27 3	540	347	16.0 s
	5 27 4	385	193	7.2 s
	5 27 5	3 104	1 240	2.9 s
	5 27 6	11 603	3 463	14.1 s
	5 27 7	0	0	22.3 s
	5 28 2	7	1
	5 28 3	34 318	8 042	224.9 s
	5 28 4	263 321	70 992	894.5 s
	5 28 5	4 388 439	210 311	2874.9 s
	5 28 6	75 720 344	1 455 113	12.7 h
	5 28 7	0	0	54.5 h
	5 29 2	21	1
	5 29 3	2 243 097	69 891	5808.2 s
	5 29 4 3	148 843	19 884	44.3 h
	5 29 5 2	36 022	31 315	1565.3 s
	5 29 6 1	120 074	119 047	403.5 s
	5 29 7	281	258	412.5 s
	5 29 8	0	0	1.0 s
	5 30 2	54	1
	5 30 3		78 086	3947.2 s
	5 30 4		3 002 015 967	60.8 d
	5 30 5		5 501 626 305	645.8 d
	5 30 6		197 049 834	211.8 d
	5 30 7		18 857	165.0 h
	5 30 8		0	72.9 s
	6 37 2	1	1
	6 37 3	231	231	6.0 h
	6 37 4	13	13	6.2 s

Table 1 :

 1 Detailed computational results (cont.)

	v N	k δ	# CA	# UCA CPU time
	6 37 5	0	0	0.10 s
	6 38 2	3	1
	6 38 3	30 491	21 371	156.0 h
	6 38 4	8 865	6 215	1074.0 s
	6 38 5	0	0	143.7 s
	6 39 2	7	1
	6 39 3	5 128 096	1 644 791	82.1 d
	6 39 4	48 249 923	19 197 035	211.7 h
	6 39 5	289	158	248.1 h
	6 39 6	0	0	4.3 s
	6 40 2	21	1
	6 40 3	747 865 015	57 025 160	362.3 d
	6 40 4 2	471 192 731	85 773 975 19213.0 d
	6 40 5 1	388	128	192.1 d
	6 40 6	0	0	10.9 s
	6 41 2	54	1
	6 41 3		581 769 269	756.9 d
	6 41 4 3		1 771 354 037	3750.0 d †
	6 41 5 2		61 351	541.7 d †
	6 41 6 1		16	1154.5 s †
	6 41 7		0	0.33 s

Table 3 :

 3 Lower bounds on UCAN(k, v) for 4 ≤ k ≤ 10 and 3 ≤ v ≤ 6 percentages of non-isomorphic arrays that are uniform are 84.61, 91.69, 91.81, and 54.67, respectively.

			11	12	12	13	13	14
	4	16	16	19	21	22	22	22
	5	25	25	25	29	31	32	32
	6	37	39	41	42	42	44	45

Acknowledgment

The authors wish to thank the referees for useful comments that helped improve this article.

and Academy of Finland, Project #289002. † Supported in part by an NSERC discovery grant.

‡ ANR-17-CE40-0022 § Present address: Mankkaanmalmi 8 A, 02180 Espoo, Finland ¶ Supported in part by the Academy of Finland, Project #289002. Supported in part by an NSERC discovery grant.