Automorphisms of higher‐dimensional Hadamard matrices

This article derives from first principles a definition of equivalence for higher‐dimensional Hadamard matrices and thereby a definition of the automorphism group for higher‐dimensional Hadamard matrices. Our procedure is quite general and could be applied to other kinds of designs for which there are no established definitions for equivalence or automorphism. Given a two‐dimensional Hadamard matrix H of order ν, there is a Product Construction which gives an order ν proper n‐dimensional Hadamard matrix P⁽ⁿ⁾(H). We apply our ideas to the matrices P⁽ⁿ⁾(H). We prove that there is a constant c > 1 such that any Hadamard matrix H of order ν > 2 gives rise via the Product Construction to cν inequivalent proper three‐dimensional Hadamard matrices of order ν. This corrects an erroneous assertion made in the literature that ”P⁽ⁿ⁾(H) is equivalent to “P⁽ⁿ⁾(H′) whenever H is equivalent to H′.” We also show how the automorphism group of P⁽ⁿ⁾(H) depends on the structure of the automorphism group of H. As an application of the above ideas, we determine the automorphism group of P⁽ⁿ⁾(Hk) when Hk is a Sylvester Hadamard matrix of order 2^k. For ν = 4, we exhibit three distinct families of inequivalent Product Construction matrices P⁽ⁿ⁾(H) where H is equivalent to H₂. These matrices each have large but non‐isomorphic automorphism groups. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 507–544, 2008     

Williamson Matrices and a Conjecture of Ito's

We point out an interesting connection between Williamson matrices and relative difference sets in nonabelian groups. As a consequence, we are able to show that there are relative (4t, 2, 4t, 2t)-difference sets in the dicyclic groups Q _8t = a, b|a ^4t = b ⁴ = 1, a ^2t = b ², b ^-1ab = a^-1 for all t of the form t = 2^a · 10 ^b · 26 ^c · m with a, b, c 0, m 1\ (mod 2), whenever 2m-1 or 4m-1 is a prime power or there is a Williamson matrix over _m. This gives further support to an important conjecture of Ito IT5 which asserts that there are relative (4t, 2, 4t, 2t)-difference sets in Q _8t for every positive integer t. We also give simpler alternative constructions for relative (4t, 2, 4t, 2t)-difference sets in Q _8t for all t such that 2t - 1 or 4t - 1 is a prime power. Relative difference sets in Q _8t with these parameters had previously been obtained by Ito IT1. Finally, we verify Ito's conjecture for all t 46.     

On the existence of Hadamard matrices

Given any natural number q > 3 we show there exists an integer t ? [2log₂(q ? 3)] such that an Hadamard matrix exists for every order 2^sq where s > t. The Hadamard conjecture is that s = 2.This means that for each q there is a finite number of orders 2^υq for which an Hadamard matrix is not known. This is the first time such a statement could be made for arbitrary q.In particular it is already known that an Hadamard matrix exists for each 2^sq where if q = 2^m ? 1 then s ? m, if q = 2^m + 3 (a prime power) then s ? m, if q = 2^m + 1 (a prime power) then s ? m + 1.It is also shown that all orthogonal designs of types (a, b, m ? a ? b) and (a, b), 0 ? a + b ? m, exist in orders m = 2^t and 2^t+2 · 3, t ? 1 a positive integer.     

Classification of reflexible regular embeddings and self-Petrie dual regular embeddings of complete bipartite graphs

In this paper, we classify the reflexible regular orientable embeddings and the self-Petrie dual regular orientable embeddings of complete bipartite graphs. The classification shows that for any natural number n, say (p₁,p₂,…,p_k are distinct odd primes and a_i>0 for each i?1), there are t distinct reflexible regular embeddings of the complete bipartite graph K_n,n up to isomorphism, where t=1 if a=0, t=2^k if a=1, t=2^k+1 if a=2, and t=3·2^k+1 if a?3. And, there are s distinct self-Petrie dual regular embeddings of K_n,n up to isomorphism, where s=1 if a=0, s=2^k if a=1, s=2^k+1 if a=2, and s=2^k+2 if a?3.     

On the asymptotic existence of cocyclic Hadamard matrices

Let q be an odd natural number. We prove there is a cocyclic Hadamard matrix of order ²10+tq whenever . We also show that if the binary expansion of q contains N ones, then there is a cocyclic Hadamard matrix of order ²4N−2q.     

Hadamard Matrices and Dihedral Groups

Let D _2p be a dihedral group of order 2p, where p is an odd integer. Let ZD _2p be the group ring of D _2p over the ring Z of integers. We identify elements of ZD _2p and their matrices of the regular representation of ZD _2p . Recently we characterized the Hadamard matrices of order 28 ([6] and [7]). There are exactly 487 Hadamard matrices of order 28, up to equivalence. In these matrices there exist matrices with some interesting properties. That is, these are constructed by elements of ZD ₆. We discuss relation of ZD _2p and Hadamard matrices of order n=8p+4, and give some examples of Hadamard matrices constructed by dihedral groups.     

Universally bad integers and the 2-adics

In his 1964 paper, de Bruijn (Math. Comp. 18 (1964) 537) called a pair (a,b) of positive odd integers good, if , where is the set of nonnegative integers whose 4-adic expansion has only 0's and 1's, otherwise he called the pair (a,b) bad. Using the 2-adic integers we obtain a characterization of all bad pairs. A positive odd integer u is universally bad if (ua,b) is bad for all pairs of positive odd integers a and b. De Bruijn showed that all positive integers of the form u=2^k+1 are universally bad. We apply our characterization of bad pairs to give another proof of this result of de Bruijn, and to show that all integers of the form u=φ_p^k(4) are universally bad, where p is prime and φ_n(x) is the nth cyclotomic polynomial. We consider a new class of integers we call de Bruijn universally bad integers and obtain a characterization of such positive integers. We apply this characterization to show that the universally bad integers u=φ_p^k(4) are in fact de Bruijn universally bad for all primes p>2. Furthermore, we show that the universally bad integers φ_2^k(4), and more generally, those of the form 4^k+1, are not de Bruijn universally bad.     

Heilbronn's conjecture on Waring's number (mod p)

Let p be a prime k|p−1, t=(p−1)/k and γ(k,p) be the minimal value of s such that every number is a sum of s kth powers . We prove Heilbronn's conjecture that γ(k,p)?k1/2 for t>2. More generally we show that for any positive integer q, γ(k,p)?C(q)k1/q for ?(t)?q. A comparable lower bound is also given. We also establish exact values for γ(k,p) when ?(t)=2. For instance, when t=3, γ(k,p)=a+b−1 where a>b>0 are the unique integers with a²+b²+ab=p, and when t=4, γ(k,p)=a−1 where a>b>0 are the unique integers with a²+b²=p.     

A weak difference set construction for higher dimensional designs

We continue the analysis of de Launey's modification of development of designs modulo a finite groupH by the action of an abelian extension function (AEF), and of the proper higher dimensional designs which result.We extend the characterization of allAEFs from the cyclic group case to the case whereH is an arbitrary finite abelian group.We prove that ourn-dimensional designs have the form (f(j ₁ j ₂ ...j _n )) (j _i J), whereJ is a subset of cardinality |H| of an extension groupE ofH. We say these designs have a weak difference set construction.We show that two well-known constructions for orthogonal designs fit this development scheme and hence exhibit families of such Hadamard matrices, weighing matrices and orthogonal designs of orderv for which |E|=2v. In particular, we construct proper higher dimensional Hadamard matrices for all orders 4t100, and conference matrices of orderq+1 whereq is an odd prime power. We conjecture that such Hadamard matrices exist for all ordersv0 mod 4.     

Complex Hadamard matrices

R. J. Turyn introduced complex Hadamard matrices and showed that if there is a complex Hadamard matrix of order c and a real Hadamard matrix of order h> > 1, then there is a real Hadamard matrix of order he. Previously, complex Hadamard matrices were only known for a few small orders and the orders for which symmetric conference matrices were known. These latter are known only to exist for orders which can be written as 1+a² +b² where a, b are integers. We give many constructions for new infinite classes of complex Hadamard matrices and show that they exist for orders 306,650, 870,1406,2450 and 3782: for the orders 650, 870, 2450 and 3782, a symmetric conference matrix cannot exist.     

On left Hadamard transversals in non-solvable groups

Let G be a group of order 4n and t an involution of G. A 2n-subset R of G is called a left Hadamard transversal of G with respect to 〈t〉 if G=R〈t〉 and for some subsets S₁ and S₂ of G. Let H be a subgroup of G such that G=[G,G]H, t∈H, and t^G⊄H, where t^G is the conjugacy class of t and [G,G] is the commutator subgroup of G. In this article, we show that if R satisfies a condition , then R is a (2n,2,2n,n) relative difference set and one can construct a v×v integral matrix B such that BB^T=B^TB=(n/2)I, where v is a positive integer determined by H and t^G (see Theorem 2.6). Using this we show that there is no left Hadamard transversal R satisfying (*) in some simple groups.     

Ryser's embedding problem for Hadamard matrices

What is the minimum order of a Hadamard matrix that contains an a by b submatrix of all 1's? Newman showed that where c^? denotes the smallest order greater than or equal to c for which a Hadamard matrix exists. It follows that if 4 divides both a and b, and if the Hadamard conjecture is true, then . We establish the improved bounds for min {a,b} ≥ 2. The Hadamard conjecture therefore implies that if 4 divides both 2ab and ?a/2? ?b/2?, then (a, b) = 2 · max {?a/2?b, ?b/2?a}. Our lower bound comes from a counting argument, while our upper bound follows from a sub‐multiplicative property of : Improvements in our upper bound occur when suitable conference matrices or Bush‐type Hadamard matrices exist. We conjecture that any (1,?1)‐matrix of size a by b occurs as a submatrix of some Hadamard matrix of order at most . © 2005 Wiley Periodicals, Inc. J Combin Designs     

Gold codes,Hadamard partitions and the security of CDMA systems

Let V = {1, 2, . . . , M} and let be a set of Hadamard matrices with the property that the magnitude of the dot product of any two rows of distinct matrices is bounded above. A Hadamard partition is any partition of the set of all rows of the matrices H _i into Hadamard matrices. Such partitions have an application to the security of quasi-synchronous code-division multiple-access radio systems when loosely synchronized (LS) codes are used as spreading codes. A new generation of LS code can be used for each information bit to be spread. For each generation, a Hadamard matrix from some partition is selected for use in the code construction. This code evolution increases security against eavesdropping and jamming. One security aspect requires that the number of Hadamard partitions be large. Thus the number of partitions is studied here. If a Kerdock code construction is used for the set of matrices, the Hadamard partition constructed is shown to be unique. It is also shown here that this is not the case if a Gold (or Gold-like) code construction is used. In this case the number of Hadamard partitions can be enumerated, and is very large.      

Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts

A generalized Davenport-Schinzel sequence is one over a finite alphabet whose subsequences are not isomorphic to a forbidden subsequence σ. What is the maximum length of such a σ-free sequence, as a function of its alphabet size n? Is the extremal function linear or nonlinear? And what characteristics of σ determine the answers to these questions? It is known that such sequences have length at most n⋅²(α(n))^O(1), where α is the inverse-Ackermann function and the O(1) depends on σ.We resolve a number of open problems on the extremal properties of generalized Davenport-Schinzel sequences. Among our results:

1.

We give a nearly complete characterization of linear and nonlinear σ∈^?{a,b,c} over a three-letter alphabet. Specifically, the only repetition-free minimally nonlinear forbidden sequences are ababa and abcacbc.

2.

We prove there are at least four minimally nonlinear forbidden sequences.

3.

We prove that in many cases, doubling a forbidden sequence has no significant effect on its extremal function. For example, Nivasch?s upper bounds on alternating sequences of the form t(ab) and t(ab)a, for t?3, can be extended to forbidden sequences of the form t(aabb) and t(aabb)a.

4.

Finally, we show that the absence of simple subsequences in σ tells us nothing about σ?s extremal function. For example, for any t, there exists a σt avoiding ababa whose extremal function is Ω(n⋅²αt(n)).

Most of our results are obtained by translating questions about generalized Davenport-Schinzel sequences into questions about the density of 0-1 matrices avoiding certain forbidden submatrices. We give new and often tight bounds on the extremal functions of numerous forbidden 0-1 matrices.     

A Galerkin Approximation for the Initial-Value Problem for Linear Second-Order Differential Equations

In this paper, a Galerkin type algorithm is given for the numerical solution of L(x)=(r(t)x'(t))'-p(t)x(t)=g(t); x(a)=x_a, x'(a)=x'_a, where r (t)>f0, and Spline hat functions form the approximating basis. Using the related quadratic form, a two-step difference equation is derived for the numerical solutions. A discrete Gronwall type lemma is then used to show that the error at the node points satisfies e_k=0(h²). If e(t) is the error function on a?t?b; it is also shown (in a variety of norms) that e(t)?Ch² and e'(t)?C₁h. Test case runs are also included. A (one step) Richardson or Rhomberg type procedure is used to show that e^R_k=0(h⁴). Thus our results are comparable to Runge-Kutta with half the function evaluations.     

A general approach to optimal control of a regression experiment

Let $\text{θ}\text{θ}\text{?}$ = ($\text{θ}\text{θ}\text{?}$₁, $\text{θ}\text{θ}\text{?}$₂, …, $\text{θ}\text{θ}\text{?}$_n)′ be the least-squares estimator of θ = (θ₁, θ₂, …, θ_n)′ by the realization of the process y(t) = Σ_{k = 1}ⁿθ_kf_k(t) + ξ(t) on the interval T = [a, b] with f = (f₁, f₂, …, f_n)′ belonging to a certain set X. The process satisfies E(ξ(t))≡0 and has known continuous covariance r(s, t) = E(ξ(s)ξ(t)) on T × T. In this paper, A-, D-, and D_s-optimality are used as criteria for choosing f in X. A-, D-, and D_s-optimal models can be constructed explicitly by means of r.     

On the solutions of a system of two Diophantine equations

We obtain all positive integer solutions(m1,m2,a,b)with ab,gcd(a,b)=1 to the system of Diophantine equations km21-lat1bt2a2r=C1,km22-lat1bt2b2r=C2,with C1,C2∈{-1,1,-2,2,-4,4},and k,l,t1,t2,r∈Z such that k0,l0,r0,t10,t2 0,gcd(k,l)=1,and k is square-free.     

Newman's phenomenon for generalized Thue-Morse sequences

Let t_j=(-1)^s(j) be the Thue-Morse sequence with s(j) denoting the sum of the digits in the binary expansion of j. A well-known result of Newman [On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc. 21 (1969) 719-721] says that t₀+t₃+t₆+?+t_3k>0 for all k?0.In the first part of the paper we show that t₁+t₄+t₇+?+t_3k+1<0 and t₂+t₅+t₈+?+t_3k+2?0 for k?0, where equality is characterized by means of an automaton. This sharpens results given by Dumont [Discrépance des progressions arithmétiques dans la suite de Morse, C. R. Acad. Sci. Paris Sér. I Math. 297 (1983) 145-148]. In the second part we study more general settings. For a,g?2 let ω_a=exp(2πi/a) and , where s_g(j) denotes the sum of digits in the g-ary digit expansion of j. We observe trivial Newman-like phenomena whenever a|(g-1). Furthermore, we show that the case a=2 inherits many Newman-like phenomena for every even g?2 and large classes of arithmetic progressions of indices. This, in particular, extends results by Drmota and Ska?ba [Rarified sums of the Thue-Morse sequence, Trans. Amer. Math. Soc. 352 (2000) 609-642] to the general g-case.