Properties of complete sets of mutually equiorthogonal frequency hypercubes

A complete set of mutually equiorthogonal frequency hypercubes (MEFH) of ordern and dimensiond, usingm distinct symbols, has (n−1) ^d /(m−1) hypercubes. In this article, we explore the properties of complete sets of MEFH. As a consequence of these properties, we show that existence of such a set implies that the number of symbolsm is a prime power. We also establish an equivalence between existence of a complete set of MEFH and existence of a certain complete set of Latin hypercubes and a certain complete orthogonal array.     

Equiorthogonal Frequency Hypercubes: Preliminary Theory

Using a strong definition of frequency hypercube, we define a strengthened form of orthogonality, called equiorthogonality, for sets of such hypercubes. We prove that the maximum possible number of mutually equiorthogonal frequency hypercubes (MEFH) of order n and dimension d based on m distinct symbols is (n-1)^d/(m-1). A set of (n-1)^d/(m-1) such MEFH is called a complete set. Because of the stronger conditions on the hypercubes, we can find complete sets of MEFH of all lower dimensions within any complete set of MEFH; this useful property is not shared by sets of mutually orthogonal hypercubes using the usual, weaker definition.     

The geometry of sets of orthogonal frequency hypercubes

We extend the notion of a framed net, introduced by D. Jungnickel, V. C. Mavron, and T. P. McDonough, J Combinatorial Theory A, 96 (2001), 376–387, to that of a d‐framed net of type ?, where d ≥ 2 and 1 ≤ ? ≤ d‐1, and we establish a correspondence between d‐framed nets of type ? and sets of mutually orthogonal frequency hypercubes of dimension d. We provide a new proof of the maximal size of a set of mutually orthogonal frequency hypercubes of type ? and dimension d, originally established by C. F. Laywine, G. L. Mullen, and G. Whittle, Monatsh Math 119 (1995), 223–238, and we obtain a geometric characterization of the framed net when this bound is satisfied as a PBIBD based on a d‐class association Hamming scheme H(d,n). © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 449–459, 2007     

Complete Sets of Mutually Orthogonal Hypercubes and Their Connections to Affine Resolvable Designs

. Recently, Laywine and Mullen proved several generalizations of Bose's equivalence between the existence of complete sets of mutually orthogonal Latin squares of order n and the existence of affine planes of order n. Laywine further investigated the relationship between sets of orthogonal frequency squares and affine resolvable balanced incomplete block designs. In this paper we generalize several of Laywine's results that were derived for frequency squares. We provide sufficient conditions for construction of an affine resolvable design from a complete set of mutually orthogonal Youden frequency hypercubes; we also show that, starting with a complete set of mutually equiorthogonal frequency hypercubes, an analogous construction can always be done. In addition, we give conditions under which an affine resolvable design can be converted to a complete set of mutually orthogonal Youden frequency hypercubes or a complete set of mutually equiorthogonal frequency hypercubes.     

On the dimension of affine resolvable designs and hypercubes

The equivalence between complete sets of mutually orthogonal hypercubes and affine resolvable designs, which generalizes the well-known equivalence between complete sets of mutually orthogonal latin squares and affine planes, is used to examine the dimension of designs by studying the prime classes in the associated hypercubes. Particular attention is given to designs of order n=9 including a design which is nonisomorphic to AG(3, 9) even though it possesses the same parameters and three prime classes. © 1996 John Wiley & Sons, Inc.     

Sets of orthogonal hypercubes of class r

A (d,n,r,t)-hypercube is an n×n×?×n (d-times) array on nr symbols such that when fixing t coordinates of the hypercube (and running across the remaining d−t coordinates) each symbol is repeated nd−r−t times. We introduce a new parameter, r, representing the class of the hypercube. When r=1, this provides the usual definition of a hypercube and when d=2 and r=t=1 these hypercubes are Latin squares. If d?2r, then the notion of orthogonality is also inherited from the usual definition of hypercubes. This work deals with constructions of class r hypercubes and presents bounds on the number of mutually orthogonal class r hypercubes. We also give constructions of sets of mutually orthogonal hypercubes when n is a prime power.     

Affine geometries and sets of equiorthogonal frequency hypercubes

Equiorthogonal frequency hypercubes are one particular generalization of orthogonal latin squares. A complete set of mutually equiorthogonal frequency hypercubes (MEFH) of order n and dimension d, using m distinct symbols, has (n − 1)^d/(m − 1) hypercubes. In this article, we prove that an affine geometry of dimension dh over 𝔽_m can always be used to construct a complete set of MEFH of order m^h and dimension d, using m distinct symbols. We also provide necessary and sufficient conditions for a complete set of MEFH to be equivalent to an affine geometry. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 435–441, 2000     

A note on orthogonal sets of hypercubes

Mutually orthogonal sets of hypercubes are higher dimensional generalizations of mutually orthogonal sets of Latin squares. For Latin squares, it is well known that the Cayley table of a group of order n is a Latin square, which has no orthogonal mate if n is congruent to 2 modulo 4. We will prove an analogous result for hypercubes. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 231–233, 1997     

On the number of SQSs,latin hypercubes and MDS codes

We establish that the logarithm of the number of latin d‐cubes of order n is and the logarithm of the number of sets of t ( is fixed) orthogonal latin squares of order n is . Similar estimations are obtained for systems of mutually strongly orthogonal latin d‐cubes. As a consequence, we construct a set of Steiner quadruple systems of order n such that the logarithm of its cardinality is as and .     

Point sets with uniformity properties and orthogonal hypercubes

The theory of (t, m, s)-nets is useful in the study of sets of points in the unit cube with small discrepancy. It is known that the existence of a (0, 2,s)-net in baseb is equivalent to the existence ofs–2 mutually orthogonal latin squares of orderb. In this paper we generalize this equivalence by showing that fort0 the existence of a (t, t+2,s)-net in baseb is equivalent to the existence ofs mutually orthogonal hypercubes of dimensiont+2 and orderb. Using the theory of hypercubes we obtain upper bounds ons for the existence of such nets. Forb a prime power these bounds are best possible. We also state several open problems.This author would like to thank the Mathematics Department of the University of Tasmania for its hospitality during his sabbatical when this paper was written. The same author would also like to thank the NSA for partial support under grant agreement # MDA904-87-H-2023.This author's research was supported by a grant from the Commonwealth of Australia through the Australian Research Council.     

Orthogonal packings inPG(5, 2)

Aspread inPG(n, q) is a set of lines which partitions the point set. A packing inPG(n, q) (n odd) is a partition of the lines into spreads. Two packings ofPG(n, q) are calledorthogonal if and only if any two spreads, one from each packing, have at most one line in common. Recently, R. D. Baker has shown the existence of a pair of orthogonal packings inPG(5, 2). In this paper we enumerate all packings inPG(5, 2) having both an automorphism of order 31 and the Frobenius automorphism. We find all pairs of orthogonal packings of the above type and display a set of six mutually orthogonal packings. Previously the largest set of orthogonal packings known inPG(5, 2) was two.     

An acyclicity theorem for cell complexes ind dimension

LetC be a cell complex ind-dimensional Euclidean space whose faces are obtained by orthogonal projection of the faces of a convex polytope ind+ 1 dimensions. For example, the Delaunay triangulation of a finite point set is such a cell complex. This paper shows that the in_front/behind relation defined for the faces ofC with respect to any fixed viewpointx is acyclic. This result has applications to hidden line/surface removal and other problems in computational geometry.Research reported in this paper was supported by the National Science Foundation under grant CCR-8714565     

Sudoku-like arrays,codes and orthogonality

This paper is concerned with constructions and orthogonality of generalized Sudoku arrays of various forms. We characterize these arrays based on their constraints; for example Sudoku squares are characterized by having strip and sub-square constraints. First, we generalize Sudoku squares to be multi-dimensional arrays with strip and sub-cube constraints and construct mutually orthogonal sets of these arrays using linear polynomials. We add additional constraints motivated by elementary intervals for low discrepancy sequences and again give a construction of these arrays using linear polynomials in detail for 3 dimensional and a general construction method for arbitrary dimension. Then we give a different construction of these hypercubes due to MDS codes. We also analyze the orthogonality of all of the Sudoku-like hypercubes we consider in this paper.     

Orthogonal systems

An equidistant permutation array (E.P.A.)A(r, v) is av × r array in which every row is a permutation of the integers 1, 2, ,r such that any two distinct rows have precisely columns in common. In this paper we introduce the concept of orthogonality for E.P.A.s. A special case of this is the well known idea of a set of pairwise orthogonal latin squares. We show that a set of these arrays is equivalent to a particular type of resolvable (r, )-design. It is also shown that the cardinality of such a set is bounded byr – with the upper bound being obtained only if = 0. A brief survey of related orthogonal systems is included. In particular, sets of pairwise orthogonal symmetric latin squares, sets of orthogonal Steiner systems and sets of orthogonal skeins.     

The Cardinality of Sets of <Emphasis Type="Italic">k</Emphasis>-Independent Vectors over Finite Fields

A set of vectors is k-independent if all its subsets with no more than k elements are linearly independent. We obtain a result concerning the maximal possible cardinality Ind _q (n, k) of a k-independent set of vectors in the n-dimensional vector space F _q ⁿ over the finite field F _q of order q. Namely, we give a necessary and sufficient condition for Ind _q (n, k) = n + 1. We conclude with some pertinent remarks re applications of our results to codes, graphs and hypercubes. Supported, in part by grants EP/C000285, NSF-DMS-0439734 and NSF-DMS-0555839. S. B. Damelin thanks the Institute for Mathematics and Applications for their hospitality.     

On the existence of MOLS with equal-sized holes

We consider a pair of MOLS (mutually orthogonal Latin squares) having holes, corresponding to missing sub-MOLS, which are disjoint and spanning It is shown that a pair of MOLS withn holes of sizeh exist forh 2 if and only ifn 4 For SOLS (self-orthogonal Latin squares) with holes, we have the same result, with two possible exceptions SOLS with 7 or 13 holes of size 6     

Designs with mutually orthogonal resolutions and decompositions of edge‐colored graphs

Two resolutions R and R^′ of a combinatorial design are called orthogonal if |R_i∩R|≤1 for all R_i∈R and R∈R^′. A set Q={R¹, R², …, R^d} of d resolutions of a combinatorial design is called a set of mutually orthogonal resolutions (MORs) if the resolutions of Q are pairwise orthogonal. In this paper, we establish necessary and sufficient conditions for the asymptotic existence of a (v, k, 1)‐BIBD with d mutually orthogonal resolutions for d≥2 and k≥3 and necessary and sufficient conditions for the asymptotic existence of a (v, k, k?1)‐BIBD with d mutually orthogonal near resolutions for d≥2 and k≥3. We use complementary designs and the most general form of an asymptotic existence theorem for decompositions of edge‐colored complete digraphs into prespecified edge‐colored subgraphs. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 425–447, 2009     

Lower Bounds For Multidimensional Zero Sums

Let f(n, d) denote the least integer such that any choice of f(n, d) elements in contains a subset of size n whose sum is zero. Harborth proved that (n-1)2 ^d +1 f(n,d) (n-1)n ^d +1. The upper bound was improved by Alon and Dubiner to c _d n. It is known that f(n-1) = 2n-1 and Reiher proved that f(n-2) = 4n-3. Only for n = 3 it was known that f(n,d) > (n-1)2 ^d +1, so that it seemed possible that for a fixed dimension, but a sufficiently large prime p, the lower bound might determine the true value of f(p,d). In this note we show that this is not the case. In fact, for all odd n 3 and d 3 we show that .     

Construction of the mutually orthogonal extraordinary supersquares

Our purpose is to determine the complete set of mutually orthogonal squares of order d, which are not necessary Latin. In this article, we introduce the concept of supersquare of order d, which is defined with the help of its generating subgroup in $\mathbb{F}_d \times \mathbb{F}_d$ . We present a method of construction of the mutually orthogonal supersquares. Further, we investigate the orthogonality of extraordinary supersquares, a special family of squares, whose generating subgroups are extraordinary. The extraordinary subgroups in $\mathbb{F}_d \times \mathbb{F}_d$ are of great importance in the field of quantum information processing, especially for the study of mutually unbiased bases. We determine the most general complete sets of mutually orthogonal extraordinary supersquares of order 4, which consist in the so-called Type I and Type II. The well-known case of d ? 1 mutually orthogonal Latin squares is only a special case, namely Type I.     

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

We describe a deterministic algorithm which, on input integersd, m and real number (0,1), produces a subset S of [m] ^d ={1,2,3,...,m} ^d that hits every combinatorial rectangle in [m] ^d of volume at least , i.e., every subset of [m] ^d the formR ₁×R ₂×...×R _d of size at least m ^d . The cardinality of S is polynomial inm(logd)/, and the time to construct it is polynomial inmd/. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables.A preliminary version of this paper appeared in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993.Research partially done while visiting the International Computer Science Institute. Research supported in part by a grant from the Israel-USA Binational Science Foundation.A large portion of this research was done while still at the International Computer Science Institute in Berkeley, California. Research supported in part by National Science Foundation operating grants CCR-9304722 and NCR-9416101, and United States-Israel Binational Science Foundation grant No. 92-00226.Supported in part by NSF under grants CCR-8911388 and CCR-9215293 and by AFOSR grants AFOSR-89-0512 AFOSR-90-0008, and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology. Research partially done while visiting the International Computer Science Institute.Partially supported by NSF NYI Grant No. CCR-9457799. Most of this research was done while the author was at MIT, partially supported by an NSF Postdoctoral Fellowship. Research partially done while visiting the International Computer Science Institute.