On locally balanced gray codes

We consider locally balanced Gray codes.We say that a Gray code is locally balanced if every “short” subword in its transition sequence contains all letters of the alphabet |1, 2,..., n~. The minimal length of these subwords is the window width of the code. We show that for each n ≥ 3 there exists a Gray code with window width at most n + 3?log n?.     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

On the Fourier spectrum of symmetric Boolean functions

We study the following questionWhat is the smallest t such that every symmetric boolean function on κ variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least 1 and at most t?We exclude the constant functions for which there is no such t and the parity functions for which t has to be κ. Let τ (κ) be the smallest such t. Our main result is that for large κ, τ (κ)≤4κ/logκ.The motivation for our work is to understand the complexity of learning symmetric juntas. A κ-junta is a boolean function of n variables that depends only on an unknown subset of κ variables. A symmetric κ-junta is a junta that is symmetric in the variables it depends on. Our result implies an algorithm to learn the class of symmetric κ-juntas, in the uniform PAC learning model, in time n ^o(κ) . This improves on a result of Mossel, O’Donnell and Servedio in [16], who show that symmetric κ-juntas can be learned in time n ^2κ/3.     

Linear closures of finite geometries

The interrelations between finite geometries (finite incidence structures) and linear codes over finite fields are discussed under some special fundamental aspects. For any incidence structure \({\mathcal{I}}\) block codes, block-difference codes and co-block codes over finite fields of characteristic p are discussed resp. introduced; correspondingly p-modular co-blocks are defined for \({\mathcal{I}}\). Orthogonality modulo p is introduced as a concept relating different geometries having the same point set. Conversely three types of block-tactical geometries may be derived from vector classes of fixed Hamming weight in a given linear code. These geometries are tactical configurations if the given code admits a transitive permutation group. A combination of both approaches leads to the concept of p-closure of a finite geometry and to the notions of p-closed, weakly p-closed and p-dense incidence structures. These geometric concepts are applied to simple or directed graphs via their natural “adjacency geometry”. Here the above mentioned code theoretic treatment leads to the concept of p-modular co-adjacent vertex sets. As instructive examples the Petersen graph, its complemetary graph and the Higman-Sims graph are considered.     

Peckness of Edge Posets

For any graded poset P, we define a new graded poset, ??(P), whose elements are the edges in the Hasse diagram of P. For any group G acting on the boolean algebra B _n in a rank-preserving fashion we conjecture that ??(B _n /G) is Peck. We prove that the conjecture holds for “common cover transitive” actions. We give some infinite families of common cover transitive actions and show that the common cover transitive actions are closed under direct and semidirect products.     

Upper bounds on the length of a shortest closed geodesic and quantitative Hurewicz theorem

In this paper we present two upper bounds on the length of a shortest closed geodesic on compact Riemannian manifolds. The first upper bound depends on an upper bound on sectional curvature and an upper bound on the volume of the manifold. The second upper bound will be given in terms of a lower bound on sectional curvature, an upper bound on the diameter and a lower bound on the volume.The related questions that will also be studied are the following: given a contractible k-dimensional sphere in M ⁿ , how “fast” can this sphere be contracted to a point, if π _i (M ⁿ )={0} for 1≤i<k. That is, what is the maximal length of the trajectory described by a point of a sphere under an “optimal” homotopy? Also, what is the “size” of the smallest non-contractible k-dimensional sphere in a (k-1)-connected manifold M ⁿ providing that M ⁿ is not k-connected?     

On distance Gray codes

A Gray code of size n is a cyclic sequence of all binary words of length n such that two consecutive words differ exactly in one position. We say that the Gray code is a distance code if the Hamming distance between words located at distance k from each other is equal to d. The distance property generalizes the familiar concepts of a locally balanced Gray code. We prove that there are no distance Gray codes with d = 1 for k > 1. Some examples of constructing distance Gray codes are given. For one infinite series of parameters, it is proved that there are no distance Gray codes.     

A class of constacyclic codes over a finite field-II

Let \(\mathbb{F}_q\) be a finite field with q = p ^m elements, where p is any prime and m ≥ 1. In this paper, we explicitly determine all the μ-constacyclic codes of length ? ⁿ over \(\mathbb{F}_q\), where ? is an odd prime coprime to p and the order of μ is a power of ?. All the repeated-root λ- constacyclic codes of length ? ⁿ p ^s over \(\mathbb{F}_q\) are also determined for any nonzero λ in \(\mathbb{F}_q\). As examples all the λ-constacyclic codes of length 3 ⁿ p ^s over \(\mathbb{F}_q\) for p = 5, 7, 11, 19 for n ≥ 1, s ≥ 1 are derived. We also obtain all the self-orthogonal negacyclic codes of length ? ⁿ over \(\mathbb{F}_q\) when q is odd prime power and give some illustrative examples.     

On the embedding of constant-weight codes into perfect codes

We show that each q-ary constant-weight code of weight 3, minimum distance 4, and length m embeds in a q-ary 1-perfect code of length n = (q ^m ? 1)/(q ? 1).     

On full-rank perfect codes over finite fields

We propose a construction of full-rank q-ary 1-perfect codes. This is a generalization of the construction of full-rank binary 1-perfect codes by Etzion and Vardy (1994). The properties of the i-components of q-ary Hamming codes are investigated, and the construction of full-rank q-ary 1-perfect codes is based on these properties. The switching construction of 1-perfect codes is generalized to the q-ary case. We propose a generalization of the notion of an i-component of a 1-perfect code and introduce the concept of an (i, σ)-component of a q-ary 1-perfect code. We also present a generalization of the Lindström–Schönheim construction of q-ary 1-perfect codes and provide a lower bound for the number of pairwise distinct q-ary 1-perfect codes of length n.     

On the summability factors of infinite series

The author has established that if [λ_n] is a convex sequence such that the series Σn ^-1λ_n is convergent and the sequence {K _n} satisfies the condition |K _n|=O[log(n+1)]^k(C, 1),k?0, whereK _n denotes the (R, logn, 1) mean of the sequence {n log (n+1)a _n}, then the series Σlog(n+1)^1-kλ_n a _n is summable |R, logn, 1|. The result obtained for the particular casek=0 generalises a previous result of the author [1].     

On the minimum size of binary codes with length 2<Emphasis Type="Italic">R</Emphasis> + 4 and covering radius <Emphasis Type="Italic">R</Emphasis>

The minimum size of a binary code with length n and covering radius R is denoted by K(n, R). For arbitrary R, the value of K(n, R) is known when n ≤  2R +  3, and the corresponding optimal codes have been classified up to equivalence. By combining combinatorial and computational methods, several results for the first open case, K(2R +  4, R), are here obtained, including a proof that K(10, 3) =  12 with 11481 inequivalent optimal codes and a proof that if K(2R +  4, R) <  12 for some R then this inequality cannot be established by the existence of a corresponding self-complementary code.     

About the length of laws for finite groups

We prove new upper bounds of the form O(n/log(n)^2?ε ) for the length of laws that hold for all groups of size at most n — improving on previous results of Bou-Rabee and Kassabov–Matucci. The methods make use of the classification of finite simple groups. Stronger bounds are proved in case the groups are assumed to be nilpotent or solvable.     

A continuation method for solving symmetric Toeplitz systems

A fast algorithm is proposed for solving symmetric Toeplitz systems. This algorithm continuously transforms the identity matrix into the inverse of a given Toeplitz matrix T. The memory requirements for the algorithm are O(n), and its complexity is O(log κ(T)nlogn), where (T) is the condition number of T. Numerical results are presented that confirm the efficiency of the proposed algorithm.     

An upper bound for the number of uniformly packed binary codes

Under study are the binary codes uniformly packed (in the wide sense) of length n with minimum distance d and covering radius ρ. It is shown that every code of this kind is uniquely determined by the set of its codewords of weights ?n/2? ? ρ, …, ?n/2? + ρ. For odd d, the number of distinct codes is at most

$2^{2^{n - \tfrac{3}{2}\log n + o(log n)} } $

.

     

Codes with the identifiable parent property for multimedia fingerprinting

Let \({\mathcal {C}}\) be a q-ary code of length n and size M, and \({\mathcal {C}}(i) = \{\mathbf{c}(i) \ | \ \mathbf{c}=(\mathbf{c}(1), \mathbf{c}(2), \ldots , \mathbf{c}(n))^{T} \in {\mathcal {C}}\}\) be the set of ith coordinates of \({\mathcal {C}}\). The descendant code of a sub-code \({\mathcal {C}}^{'} \subseteq {\mathcal {C}}\) is defined to be \({\mathcal {C}}^{'}(1) \times {\mathcal {C}}^{'}(2) \times \cdots \times {\mathcal {C}}^{'}(n)\). In this paper, we introduce a multimedia analogue of codes with the identifiable parent property (IPP), called multimedia IPP codes or t-MIPPC(n, M, q), so that given the descendant code of any sub-code \({\mathcal {C}}^{'}\) of a multimedia t-IPP code \({\mathcal {C}}\), one can always identify, as IPP codes do in the generic digital scenario, at least one codeword in \({\mathcal {C}}^{'}\). We first derive a general upper bound on the size M of a multimedia t-IPP code, and then investigate multimedia 3-IPP codes in more detail. We characterize a multimedia 3-IPP code of length 2 in terms of a bipartite graph and a generalized packing, respectively. By means of these combinatorial characterizations, we further derive a tight upper bound on the size of a multimedia 3-IPP code of length 2, and construct several infinite families of (asymptotically) optimal multimedia 3-IPP codes of length 2.     

Equiconvergence of expansions in multiple Fourier series and in fourier integrals with “lacunary sequences of partial sums”

We investigate the equiconvergence on T^N = [?π, π)^N of expansions in multiple trigonometric Fourier series and in the Fourier integrals of functions f ∈ L_p(T^N) and g ∈ L_p(R^N), p > 1, N ≥ 3, g(x) = f(x) on T^N, in the case where the “partial sums” of these expansions, i.e., S_n(x; f) and J_α(x; g), respectively, have “numbers” n ∈ Z^N and α ∈ R^N (n_j = [α_j], j = 1,..., N, [t] is the integral part of t ∈ R¹) containing N ? 1 components which are elements of “lacunary sequences.”     

Unions of Fat Convex Polytopes Have Short Skeletons

The skeleton of a polyhedral set is the union of its edges and vertices. Let \(\mathcal {P}\) be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f _max be the maximum complexity of any face of a polytope in \(\mathcal {P}\). We prove that the total length of the skeleton of the union of the polytopes in \(\mathcal {P}\) is at most O(α(n)?log^? n?logf _max) times the sum of the skeleton lengths of the individual polytopes.     

On the additive complexity of GCD and LCM matrices

In the paper, the additive complexity of matrices formed by positive integer powers of greatest common divisors and least common multiples of the indices of the rows and columns is considered. It is proved that the complexity of the n × n matrix formed by the numbers GCD^r(i, k) over the basis {x + y} is asymptotically equal to rn log²n as n→∞, and the complexity of the n × n matrix formed by the numbers LCM^r(i, k) over the basis {x + y,?x} is asymptotically equal to 2rn log₂n as n→∞.     

Depth of Boolean functions over an arbitrary infinite basis

Realization of Boolean functions by circuits is considered over an arbitrary infinite complete basis. The depth of a circuit is defined as the greatest number of functional elements constituting a directed path from an input of the circuit to its output. The Shannon function of the depth is defined for a positive integer n as the minimal depth D _B (n) of the circuits sufficient to realize every Boolean function on n variables over a basis B. It is shown that, for each infinite basis B, either there exists a constant β ? 1 such that D _B (n) = β for all sufficiently large n or there exist an integer constant γ ? 2 and a constant δ such that log _γ n ? D _B (n) ? log _γ n + δ for all n.