Combinatorial methods in the construction of point sets with uniformity properties

It is well known that (t, m, s)-nets are useful in numerical analysis. Many of the constructions of such nets arise from number theoretic or algebraic constructions. Less well known is the fact that combinatorial constructions also yield nets with very good and in many cases, optimal parameters. In this paper, we provide a survey of such combinatorial constructions of (t, m, s)-nets.     

Construction of balanced doubles schedules

A recursive construction for v-player balanced doubles schedules based on resolvable B[4, 1; v] designs is presented. The schedules are resolvable when v ≡ 4 (mod 12). Combined with special constructions for v = 54 and 55 and previously known constructions, this gives schedules for all v.     

Constructions of generalized Sidon sets

We give explicit constructions of sets S with the property that for each integer k, there are at most g solutions to k=s₁+s₂,s_i∈S; such sets are called Sidon sets if g=2 and generalized Sidon sets if g?3. We extend to generalized Sidon sets the Sidon-set constructions of Singer, Bose, and Ruzsa. We also further optimize Kolountzakis’ idea of interleaving several copies of a Sidon set, extending the improvements of Cilleruelo, Ruzsa and Trujillo, Jia, and Habsieger and Plagne. The resulting constructions yield the largest known generalized Sidon sets in virtually all cases.     

On the use of the term diastēma in ancient Greek constructions

I examine the use of the term diastēma by Greek geometers in both plane and spherical constructions. I show that while diastēma may be translated as radius in plane constructions, this will not work on the sphere. These investigations have some implications for how we think of construction in Greek mathematics in general.     

Constructions of Semi-regular Relative Difference Sets

J. A. Davis, J. Jedwab, and M. Mowbray (1998, Des. Codes Cryptogr.13, 131–146) gave two new constructions for semi-regular relative difference sets (RDSs). They asked if the two constructions could be unified. In this paper, we show that the two constructions are closely related. In fact, the second construction should be viewed as an extension of the first. Furthermore, we generalize the second construction to obtain new RDSs.     

A new product construction for partial difference sets

Relatively few constructions are known of negative Latin square type Partial Difference Sets (PDSs), and most of the known constructions are in elementary abelian groups. We present a product construction that produces negative Latin square type PDSs, and we apply this product construction to generate examples in p-groups of exponent bigger than p.     

Minimal 1-saturating sets and complete caps in binary projective spaces

In binary projective spaces PG(v,2), minimal 1-saturating sets, including sets with inner lines and complete caps, are considered. A number of constructions of the minimal 1-saturating sets are described. They give infinite families of sets with inner lines and complete caps in spaces with increasing dimension. Some constructions produce sets with an interesting symmetrical structure connected with inner lines, polygons, and orbits of stabilizer groups. As an example we note an 11-set in PG(4,2) called “Pentagon with center”. The complete classification of minimal 1-saturating sets in small geometries is obtained by computer and is connected with the constructions described.     

Constructing strength three covering arrays with augmented annealing

A covering arrayCA(N;t,k,v) is an N×k array such that every N×t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. One application of these objects is to generate software test suites to cover all t-sets of component interactions. Methods for construction of covering arrays for software testing have focused on two main areas. The first is finding new algebraic and combinatorial constructions that produce smaller covering arrays. The second is refining computational search algorithms to find smaller covering arrays more quickly. In this paper, we examine some new cut-and-paste techniques for strength three covering arrays that combine recursive combinatorial constructions with computational search; when simulated annealing is the base method, this is augmented annealing. This method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide new bounds for some strength three covering arrays.     

General frame constructions for Z-cyclic triplewhist tournaments

Frames are useful in dealing with resolvable designs such as resolvable balanced incomplete block designs and triplewhist tournaments. Z-cyclic triplewhist tournament frames are also useful in the constructions of Z-cyclic triplewhist tournaments. In this paper, the concept of an (h₁,h₂,…,hn;u)-regular Z-cyclic triplewhist tournament frame is defined, and used to establish several quite general recursive constructions for Z-cyclic triplewhist tournaments. As corollaries, we are able to unify many known constructions for Z-cyclic triplewhist tournaments. As an application, some new Z-cyclic triplewhist tournament frames and Z-cyclic triplewhist tournaments are obtained. The known existence results of such designs are then extended.     

Code constructions and existence bounds for relative generalized Hamming weight

The relative generalized Hamming weight (RGHW) of a linear code C and a subcode C ¹ is an extension of generalized Hamming weight. The concept was firstly used to protect messages from an adversary in the wiretap channel of type II with illegitimate parties. It was also applied to the wiretap network II for secrecy control of network coding and to trellis-based decoding algorithms for complexity estimation. For RGHW, bounds and code constructions are two related issues. Upper bounds on RGHW show the possible optimality for the applications, and code constructions meeting upper bounds are for designing optimal schemes. In this article, we show indirect and direct code constructions for known upper bounds on RGHW. When upper bounds are not tight or constructions are hard to find, we provide two asymptotically equivalent existence bounds about good code pairs for designing suboptimal schemes. Particularly, most code pairs (C, C ¹) are good when the length n of C is sufficiently large, the dimension k of C is proportional to n and other parameters are fixed. Moreover, the first existence bound yields an implicit lower bound on RGHW, and the asymptotic form of this existence bound generalizes the usual asymptotic Gilbert–Varshamov bound.     

Strongly regular Cayley graphs from partitions of subdifference sets of the Singer difference sets

In this paper, we give a new lifting construction of “hyperbolic” type of strongly regular Cayley graphs. Also we give new constructions of strongly regular Cayley graphs over the additive groups of finite fields based on partitions of subdifference sets of the Singer difference sets. Our results unify some recent constructions of strongly regular Cayley graphs related to m-ovoids and i-tight sets in finite geometry. Furthermore, some of the strongly regular Cayley graphs obtained in this paper are new or nonisomorphic to known strongly regular graphs with the same parameters.     

New generalized almost perfect nonlinear functions

APN (almost perfect non-linear) functions over finite fields of even characteristic are widely studied due to their applications to the design of symmetric ciphers resistant to differential attacks. This notion was recently generalized to GAPN (generalized APN) functions by Kuroda and Tsujie to odd characteristic p. They presented some constructions of GAPN functions, and other constructions were given by Zha et al. We present new constructions of GAPN functions both in the case of monomial and multinomial functions. Our monomial GAPN functions can be viewed as a further generalization of the Gold APN functions. We show that a certain technique used by Hou to construct permutations over finite fields also yields monomial GAPN functions. We also present several new constructions of GAPN functions which are sums of monomial GAPN functions, as well as new GAPN functions of degree p which can be written as the product of two powers of linearized polynomials. For this latter construction we describe some interesting differences between even and odd characteristic and also obtain a classification in certain cases.     

Applications of k-covers II

We continue the study of applications of k-covers to some topological constructions, mostly to function spaces and hyperspaces.     

Finite axiomatizability of local set theory

The need for modifying axiomatic set theories was caused, in particular, by the development of category theory. The ZF and NBG axiomatic theories turned out to be unsuitable for defining the notion of a model of category theory. The point is that there are constructions such as the category of categories in naïve category theory, while constructions like the set of sets are strongly restricted in the ZF and NBG axiomatic theories. Thus, it was required, on the one hand, to restrict constructions similar to the category of categories and, on the other hand, adapt axiomatic set theory in order to give a definition of a category which survives restricted construction similar to the category of categories. This task was accomplished by promptly inventing the axiom of universality (AU) asserting that each set is an element of a universal set closed under all NBG constructions. Unfortunately, in the theories ZF + AU and NBG + AU, there are toomany universal sets (as many as the number of all ordinals), whereas to solve the problem stated above, a countable collection of universal sets would suffice. For this reason, in 2005, the first-named author introduced local-minimal set theory, which preserves the axiom AU of universality and has an at most countable collection of universal sets. This was achieved at the expense of rejecting the global replacement axiom and using the local replacement axiom for each universal class instead. Local-minimal set theory has 14 axioms and one axiom scheme (of comprehension). It is shown that this axiom scheme can be replaced by finitely many axioms that are special cases of the comprehension scheme. The proof follows Bernays’ scheme with significant modifications required by the presence of the restricted predicativity condition on the formula in the comprehension axiom scheme.     

Two constructions of affine Lie algebra representations and boson-fermion correspondence in quantum field theory

We establish an isomorphism between the vertex and spinor representations of affine Lie algebras for types D_l⁽¹⁾and D_{l + 1}⁽²⁾. We also study decomposition of spinor representations using the infinite family of Casimir operators and prove that they are either irreducible or have two irreducible components. We show that the vertex and spinor constructions of the representations can be reformulated in the language of two-dimensional quantum field theory. In this physical context, the two constructions yield the generalized sine-Gordon and Thirring models, respectively, already in renormalized form. The isomorphism of representations implies an equivalence of these two models which is known in quantum field theory as the boson-fermion correspondence     

Large sets of t-designs through partitionable sets: A survey

The method of partitionable sets for constructing large sets of t-designs have now been used for nearly a decade. The method has resulted in some powerful recursive constructions and also existence results especially for large sets of prime sizes. Perhaps the main feature of the approach is its simplicity. In this paper, we describe the approach and show how it is employed to obtain some of the recursive theorems. We also review the existence results and recursive constructions which have been found by this method.     

A-hypergeometric functions in transcendental questions of algebraic geometry

We generalize known constructions of A-hypergeometric functions. In particular, we show that the periods of middle dimension on affine or projective complex algebraic varieties are A-hypergeometric functions of the coefficients of polynomial equations of these varieties.     

Constructing Ramsey graphs from Boolean function representations

Explicit construction of Ramsey graphs or graphs with no large clique or independent set, has remained a challenging open problem for a long time. While Erdös’ probabilistic argument shows the existence of graphs on 2n vertices with no clique or independent set of size 2 ⁿ , the best explicit constructions achieve a far weaker bound. There is a connection between Ramsey graph constructions and polynomial representations of Boolean functions due to Grolmusz; a low degree representation for the OR function can be used to explicitly construct Ramsey graphs [17,18]. We generalize the above relation by proposing a new framework. We propose a new definition of OR representations: a pair of polynomials represent the OR function if the union of their zero sets contains all points in {0, 1} ⁿ except the origin. We give a simple construction of a Ramsey graph using such polynomials. Furthermore, we show that all the known algebraic constructions, ones to due to Frankl-Wilson [12], Grolmusz [18] and Alon [2] are captured by this framework; they can all be derived from various OR representations of degree O(√n) based on symmetric polynomials. Thus the barrier to better Ramsey constructions through such algebraic methods appears to be the construction of lower degree representations. Using new algebraic techniques, we show that better bounds cannot be obtained using symmetric polynomials.     

Full Spark Frames

Finite frame theory has a number of real-world applications. In applications like sparse signal processing, data transmission with robustness to erasures, and reconstruction without phase, there is a pressing need for deterministic constructions of frames with the following property: every size-M subcollection of the M-dimensional frame elements is a spanning set. Such frames are called full spark frames, and this paper provides new constructions using the discrete Fourier transform. Later, we prove that full spark Parseval frames are dense in the entire set of Parseval frames, meaning full spark frames are abundant, even if one imposes an additional tightness constraint. Finally, we prove that testing whether a given matrix is full spark is hard for NP under randomized polynomial-time reductions, indicating that deterministic full spark constructions are particularly significant because they guarantee a property which is otherwise difficult to check.