Maximal sets of permutations constructed from projective planes

On the set of n²+n+1 points of a projective plane, a set of n²+n+1 permutations is constructed with the property that any two are a Hamming distance 2n+1 apart. Another set is constructed in which every pair are a Hamming distance not greater than 2n+1 apart. Both sets are maximal with respect to the stated property.     

The endomorphism spectrum of a monounary algebra

The endomorphism spectrum specA of an algebra A is defined as the set of all positive integers, which are equal to the number of elements in an endomorphic image of A, for all endomorphisms of A. In this paper we study finite monounary algebras and their endomorphism spectrum. If a finite set S of positive integers is given, one can look for a monounary algebra A with S = specA. We show that for countably many finite sets S, no such A exists. For some sets S, an appropriate A with spec A = S are described. For n ∈ ? it is easy to find a monounary algebra A with {1, 2, ..., n} = specA. It will be proved that if i ∈ ?, then there exists a monounary algebra A such that specA skips i consecutive (consecutive eleven, consecutive odd, respectively) numbers. Finally, for some types of finite monounary algebras (binary and at least binary trees) A, their spectrum is shown to be complete.     

Quasi-median hulls in Hamming space are Steiner hulls

A Hamming space Λⁿ consists of all sequences of length n over an alphabet Λ and is endowed with the Hamming distance. In particular, any set of aligned DNA sequences of fixed length constitutes a subspace of a Hamming space with respect to mismatch distance. The quasi-median operation returns for any three sequences u,v,w the sequence which in each coordinate attains either the majority coordinate from u,v,w or else (in the case of a tie) the coordinate of the first entry, u; for a subset of Λⁿ the iterative application of this operation stabilizes in its quasi-median hull. We show that for every finite tree interconnecting a given subset X of Λⁿ there exists a shortest realization within Λⁿ for which all interior nodes belong to the quasi-median hull of X. Hence the quasi-median hull serves as a Steiner hull for the Steiner problem in Hamming space.     

Unanimity and the Anscombe’s paradox

We establish a new sufficient condition for avoiding a generalized Anscombe’s paradox. In a situation where votes describe positions regarding finitely many yes-or-no issues, the Anscombe’s α-paradox holds if more than α% of the voters disagree on a majority of issues with the outcome of issue-wise majority voting. We define the level of unanimity of a set of votes as the number of issues minus the maximal Hamming distance between two votes. We compute for the case of large electorates the exact level of unanimity above which the Anscombe’s α-paradox never holds, whatever the distribution of individuals among votes.     

Meet-irreducible submaximal clones determined by nontrivial equivalence relations

Let θ and ρ be a nontrivial equivalence relation and a binary relation on a finite set A, respectively. It is known from Rosenberg’s classification theorem (1965) that the clone Pol θ, which consists of all operations on A that preserve θ, is among the maximal clones on A. In the present paper, we find all binary relations ρ such that the clone Pol ρ is a meet-irreducible maximal subclone of Pol θ.     

On the enumeration of certain sets of planted plane trees

Using the definition of planted plane trees given by D. A. Klarner (“A correspondence between sets of trees,” Indag. Math.31 (1969), 292–296) the number of nonisomorphic classes of certain sets of these trees is enumerated by obtaining a one-to-one correspondence between these classes and certain sets of nondecreasing vectors with integral components. A one-to-one correspondence between sets of (r + 1)-ary sequences and a certain set of planted plane trees is also established, which permits enumeration of this set. Finally, a natural generalization of Klarner's one-to-one correspondence between the above sets of trees and certain sets of edge-chromatic trees is obtained.     

Tree Complexity and a Doubly Exponential Gap between Structured and Random Sequences

This paper introduces a new complexity measure for binary sequences, the tree complexity. The tree complexity of a sequence grows asymptotically likeO(2^2h) (hthe height of the tree) for random sequences. Functions inF₂[[x]] can be identified with their coefficient sequence. Under this aspect we will show that the tree complexity isO(1) for all algebraic sequences inF^∞₂. This doubly exponential gap may serve as an indicator of “simply” structured sequences and furthermore it defines certain classes within the vast set of transcendental sequences.     

Un analogue elliptique du théorème de Roth

We present here quantitative versions, in dimension one, of Faltings' theorem according to which the set of K-rational points (where K is a given number field) of an Abelian variety A defined over K, which are close (with respect to a v-adic distance on K) to some K-subvariety X of A, but do not belong to X, is finite. More precisely, we treat the case where A is an elliptic curve and X is reduced to a point of A and we give (in this case) explicit bounds for the cardinal of the exceptional finite set. We consider also, more generally, not only one place v of K, but also a finite set S of places of K and the distance from the point of A to X, which takes into account all the places of S. To cite this article: B. Farhi, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

δ-Uniform BSS Machines

Aδ-uniform BSS machine is a standard BSS machine which does not rely on exact equality tests. We prove that, for any real closed archimedean fieldR, a set isδ-uniformly semi-decidable iff it is open and semi-decidable by a BSS machine which is locally time bounded; we also prove that the local time bound condition is nontrivial. This entails a number of results about BSS machines, in particular the existence of decidable sets whose interior (closure) is not even semi-decidable without adding constants. Finally, we show that the sets semi-decidable by Turing machines are the sets semi-decidable byδ-uniform machines with coefficients inQorT, the field of Turing computable numbers.     

New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

We give a new upper bound on the maximum size Aq(n,d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q?3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q=3,4,5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme.     

Perfect binary codes of infinite length

A subset C of infinite-dimensional binary cube is called a perfect binary code with distance 3 if all balls of radius 1 (in the Hamming metric) with centers in C are pairwise disjoint and their union cover this binary cube. Similarly, we can define a perfect binary code in zero layer, consisting of all vectors of infinite-dimensional binary cube having finite supports. In this article we prove that the cardinality of all cosets of perfect binary codes in zero layer is the cardinality of the continuum. Moreover, the cardinality of all cosets of perfect binary codes in the whole binary cube is equal to the cardinality of the hypercontinuum.     

Distance regularity of Kerdock codes

A code is called distance regular, if for every two codewords x, y and integers i, j the number of codewords z such that d(x, z) = i and d(y, z) = j, with d the Hamming distance, does not depend on the choice of x, y and depends only on d(x, y) and i, j. Using some properties of the discrete Fourier transform we give a new combinatorial proof of the distance regularity of an arbitrary Kerdock code. We also calculate the parameters of the distance regularity of a Kerdock code.     

Measure-Theoretic Properties of Level Sets of Distance Functions

We consider the level sets of distance functions from the point of view of geometric measure theory. This lays the foundation for further research that can be applied, among other uses, to the derivation of a shape calculus based on the level-set method. Particular focus is put on the \((n-1)\)-dimensional Hausdorff measure of these level sets. We show that, starting from a bounded set, all sub-level sets of its distance function have finite perimeter. Furthermore, if a uniform-density condition is satisfied for the initial set, one can even show an upper bound for the perimeter that is uniform for all level sets. Our results are similar to existing results in the literature, with the important distinction that they hold for all level sets and not just almost all. We also present an example demonstrating that our results are sharp in the sense that no uniform upper bound can exist if our uniform-density condition is not satisfied. This is even true if the initial set is otherwise very regular (i.e., a bounded Caccioppoli set with smooth boundary).     

Self-Affine Sets and Graph-Directed Systems

Abstract. A self-affine set in R ⁿ is a compact set T with A(T)= ∪ _{d∈ D} (T+d) where A is an expanding n× n matrix with integer entries and D ={d ₁ , d ₂ ,···, d _N } ? Z ⁿ is an N -digit set. For the case N = | det(A)| the set T has been studied in great detail in the context of self-affine tiles. Our main interest in this paper is to consider the case N > | det(A)| , but the theorems and proofs apply to all the N . The self-affine sets arise naturally in fractal geometry and, moreover, they are the support of the scaling functions in wavelet theory. The main difficulty in studying such sets is that the pieces T+d, d∈ D, overlap and it is harder to trace the iteration. For this we construct a new graph-directed system to determine whether such a set T will have a nonvoid interior, and to use the system to calculate the dimension of T or its boundary (if T ^o ). By using this setup we also show that the Lebesgue measure of such T is a rational number, in contrast to the case where, for a self-affine tile, it is an integer.     

A variant of the Notion of Semicreative set

This paper introduces the notion of cW10-creative set, which strengthens that of semicreative set in a similar way as complete creativity strengthens creativity. Two results are proven, both of which imply that not all semicreative sets are cW10-creative. First, it is shown that semicreative Dedekind cuts cannot be cW10-creative; the existence of semicreative Dedekind cuts was shown by Soare. Secondly, it is shown that (i) if A ⊕ B, the join of A and B, is cW10-creative, then either A or B is cW10-creative, and (ii) the same is not true with ‘cW10-creative’ replaced by ‘semicreative’. Moreover, sets A, B which provide a counterexample for (ii) can be constructed within any given nonrecursive r.e. T-degrees a, b. MSC: 03D30.     

Badness and jump inversion in the enumeration degrees

This paper continues the investigation into the relationship between good approximations and jump inversion initiated by Griffith. Firstly it is shown that there is a ${\Pi^{0}_{2}}$ set A whose enumeration degree a is bad—i.e. such that no set ${X \in a}$ is good approximable—and whose complement ${\overline{A}}$ has lowest possible jump, in other words is low₂. This also ensures that the degrees y ≤ a only contain ${\Delta^{0}_{3}}$ sets and thus yields a tight lower bound for the complexity of both a set of bad enumeration degree, and of its complement, in terms of the high/low jump hierarchy. Extending the author’s previous characterisation of the double jump of good approximable sets, the triple jump of a ${\Sigma^{0}_{2}}$ set A is characterised in terms of the index set of coinfinite sets enumeration reducible to A. The paper concludes by using Griffith’s jump interpolation technique to show that there exists a high quasiminimal ${\Delta^{0}_{2}}$ enumeration degree.     

Constructions of optimal low-hit-zone frequency hopping sequence sets

In recent years, the study relating to low-hit-zone frequency hopping sequence sets, including the bounds on the Hamming correlations within the low hit zone and the optimal constructions, has become a new research area attracting the attention of many related researchers. In this paper, two constructions of optimal frequency hopping sequence sets with low hit zone have been employed, one of which is based on m-sequence while the other is based on the decimated sequences of m-sequence. Moreover, in the special case of \(k=n-1\), the construction based on the decimated sequences of m-sequence also yields low-hit-zone frequency hopping sequence sets with optimal periodic partial Hamming correlation property.     

Wythoff partizan subtraction

We introduce a class of normal-play partizan games, called Complementary Subtraction. These games are instances of Partizan Subtraction where we take any set A of positive integers to be Left’s subtraction set and let its complement be Right’s subtraction set. In wythoff partizan subtraction we take the set A and its complement B from wythoff nim, as the two subtraction sets. As a function of the heap size, the maximum size of the canonical forms grows quickly. However, the value of the heap is either a number or, in reduced canonical form, a switch. We find the switches by using properties of the Fibonacci word and standard Fibonacci representations of integers. Moreover, these switches are invariant under shifts by certain Fibonacci numbers. The values that are numbers, however, are distinct, and we can find their binary representation in polynomial time using a representation of integers as sums of Fibonacci numbers, known as the ternary (or “the even”) Fibonacci representation.     

On the minimum average distance of binary constant weight codes

Let β(n,M,w) denote the minimum average Hamming distance of a binary constant weight code with length n, size M and weight w. In this paper, we study the problem of determining β(n,M,w). Using the methods from coding theory and linear programming, we derive several lower bounds on the average Hamming distance of a binary constant weight code. These lower bounds enable us to determine the exact value for β(n,M,w) in several cases.     

Duality between bent functions and affine functions

A Boolean function in an even number of variables is called bent if it is at the maximal possible Hamming distance from the class of all affine Boolean functions. We prove that there is a duality between bent functions and affine functions. Namely, we show that affine function can be defined as a Boolean function that is at the maximal possible distance from the set of all bent functions.