On the minimum length of some linear codes

We determine the minimum length n _q (k, d) for some linear codes with k ≥ 5 and q ≥ 3. We prove that n _q (k, d) = g _q (k, d) + 1 for when k is odd, for when k is even, and for . This work was supported by the Korea Research Foundation Grant funded by the Korean Government(MOEHRD). (KRF-2005-214-C00175). This research has been partially supported by Grant-in-Aid for Scientific Research of Japan Society for the Promotion of Science under Contract Number 17540129.     

Maximal partial packings of $${Z_2^n}$$ with perfect codes

A maximal partial Hamming packing of is a family of mutually disjoint translates of Hamming codes of length n, such that any translate of any Hamming code of length n intersects at least one of the translates of Hamming codes in . The number of translates of Hamming codes in is the packing number, and a partial Hamming packing is strictly partial if the family does not constitute a partition of . A simple and useful condition describing when two translates of Hamming codes are disjoint or not disjoint is proved. This condition depends on the dual codes of the corresponding Hamming codes. Partly, by using this condition, it is shown that the packing number p, for any maximal strictly partial Hamming packing of , n = 2 ^m −1, satisfies . It is also proved that for any n equal to 2 ^m −1, , there exist maximal strictly partial Hamming packings of with packing numbers n−10,n−9,n−8,...,n−1. This implies that the upper bound is tight for any n = 2 ^m −1, . All packing numbers for maximal strictly partial Hamming packings of , n = 7 and 15, are found by a computer search. In the case n = 7 the packing number is 5, and in the case n = 15 the possible packing numbers are 5,6,7,...,13 and 14.      

Explicit constructions of separating hash families from algebraic curves over finite fields

Let X be a set of order n and Y be a set of order m. An (n,m,{w ₁, w ₂})-separating hash family is a set of N functions from X to Y such that for any with , |X ₁| = w ₁ and |X ₂| = w ₂, there exists an element such that . In this paper, we provide explicit constructions of separating hash families using algebraic curves over finite fields. In particular, applying the Garcia–Stichtenoth curves, we obtain an infinite class of explicitly constructed (n,m,{w ₁,w ₂})–separating hash families with for fixed m, w ₁, and w ₂. Similar results for strong separating hash families are also obtained. As consequences of our main results, we present explicit constructions of infinite classes of frameproof codes, secure frameproof codes and identifiable parent property codes with length where n is the size of the codes. In fact, all the above explicit constructions of hash families and codes provide the best asymptotic behavior achieving the bound , which substantially improve the results in [ 8, 15, 17] give an answer to the fifth open problem presented in [11].     

Algebraic-geometry codes, one-point codes, and evaluation codes

One-point codes are those algebraic-geometry codes for which the associated divisor is a non-negative multiple of a single point. Evaluation codes were defined in order to give an algebraic generalization of both one-point algebraic-geometry codes and Reed–Muller codes. Given an -algebra A, an order function on A and given a surjective -morphism of algebras , the ith evaluation code with respect to is defined as the code . In this work it is shown that under a certain hypothesis on the -algebra A, not only any evaluation code is a one-point code, but any sequence of evaluation codes is a sequence of one-point codes. This hypothesis on A is that its field of fractions is a function field over and that A is integrally closed. Moreover, we see that a sequence of algebraic-geometry codes G _i with associated divisors is the sequence of evaluation codes associated to some -algebra A, some order function and some surjective morphism with if and only if it is a sequence of one-point codes.      

Two results on maximum nonlinear functions

Maximum nonlinear functions are widely used in cryptography because the coordinate functions F _β (x) := tr(β F(x)), , have large distance to linear functions. Moreover, maximum nonlinear functions have good differential properties, i.e. the equations F(x + a) − F(x) = b, , have 0 or 2 solutions. Two classes of maximum nonlinear functions are the Gold power functions , gcd(k, m) = 1, and the Kasami power functions , gcd(k, m) = 1. The main results in this paper are: (1) We characterize the Gold power functions in terms of the distance of their coordinate functions to characteristic functions of subspaces of codimension 2 in . (2) We determine the differential properties of the Kasami power functions if gcd(k,m) ≠ 1.      

A new extension theorem for 3-weight modulo q linear codes over $${\mathbb{F}_ q}$$

We prove that every [n, k, d] _q code with q ≥ 4, k ≥ 3, whose weights are congruent to 0, −1 or −2 modulo q and is extendable unless its diversity is for odd q, where .      

Another construction for large sets of Kirkman triple systems

A large set of Kirkman triple systems of order v, denoted by LKTS(v), is a collection , where every is a KTS(v) and all form a partition of all triples on X. In this article, we give a new construction for LKTS(6v + 3) via OLKTS(2v + 1) with a special property and obtain new results for LKTS, that is there exists an LKTS(3v) for , where p, q ≥ 0, r _i , s _j ≥ 1, q _i is a prime power and mod 12.      

Efficient <Emphasis Type="Italic">p</Emphasis>th root computations in finite fields of characteristic <Emphasis Type="Italic">p</Emphasis>

We present a method for computing pth roots using a polynomial basis over finite fields of odd characteristic p, p ≥ 5, by taking advantage of a binomial reduction polynomial. For a finite field extension of our method requires p − 1 scalar multiplications of elements in by elements in . In addition, our method requires at most additions in the extension field. In certain cases, these additions are not required. If z is a root of the irreducible reduction polynomial, then the number of terms in the polynomial basis expansion of z ^1/p , defined as the Hamming weight of z ^1/p or , is directly related to the computational cost of the pth root computation. Using trinomials in characteristic 3, Ahmadi et al. (Discrete Appl Math 155:260–270, 2007) give is greater than 1 in nearly all cases. Using a binomial reduction polynomial over odd characteristic p, p ≥ 5, we find always.      

Another hybrid conjugate gradient algorithm for unconstrained optimization

Another hybrid conjugate gradient algorithm is subject to analysis. The parameter β _k is computed as a convex combination of (Hestenes-Stiefel) and (Dai-Yuan) algorithms, i.e. . The parameter θ _k in the convex combination is computed in such a way so that the direction corresponding to the conjugate gradient algorithm to be the Newton direction and the pair (s _k , y _k ) to satisfy the quasi-Newton equation , where and . The algorithm uses the standard Wolfe line search conditions. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms the Hestenes-Stiefel and the Dai-Yuan conjugate gradient algorithms as well as the hybrid conjugate gradient algorithms of Dai and Yuan. A set of 750 unconstrained optimization problems are used, some of them from the CUTE library.      

Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits

Let p be a prime and let be an elliptic curve defined over the finite field of p elements. For a given point the linear congruential genarator on elliptic curves (EC-LCG) is a sequence (U _n ) of pseudorandom numbers defined by the relation: where denote the group operation in and is the initial value or seed. We show that if G and sufficiently many of the most significants bits of two consecutive values U _n , U _n+1 of the EC-LCG are given, one can recover the seed U ₀ (even in the case where the elliptic curve is private) provided that the former value U _n does not lie in a certain small subset of exceptional values. We also estimate limits of a heuristic approach for the case where G is also unknown. This suggests that for cryptographic applications EC-LCG should be used with great care. Our results are somewhat similar to those known for the linear and non-linear pseudorandom number congruential generator.      

A two-to-one map and abelian affine difference sets

Let D be an affine difference set of order n in an abelian group G relative to a subgroup N. Set = H \ {1, ω}, where H = G/N and . Using D we define a two-to-one map g from to N. The map g satisfies g(σ ^m ) = g(σ) ^m and g(σ) = g(σ ⁻¹) for any multiplier m of D and any element σ ∈ . As applications, we present some results which give a restriction on the possible order n and the group theoretic structure of G/N.      

A generalization of Meshulam’s theorem on subsets of finite abelian groups with no 3-term arithmetic progression

Let r ₁, …, r _s be non-zero integers satisfying r ₁ + ⋯ + r _s = 0. Let G be a finite abelian group with k _i |k _i-1(2 ≤ i ≤ n), and suppose that (r _i , k ₁) = 1(1 ≤ i ≤ s). Let denote the maximal cardinality of a set which contains no non-trivial solution of r ₁ x ₁ + ⋯ + r _s x _s = 0 with . We prove that . We also apply this result to study problems in finite projective spaces.      

Embeddings of resolvable group divisible designs with block size 3

It is proved in this paper that an RGD(3, g;v) can be embedded in an RGD(3, g;u) if and only if , , , v ≥ 3g, u ≥ 3v, and (g,v) ≠ (2,6),(2,12),(6,18).     

Bifurcations of Positive and Negative Continua in Quasilinear Elliptic Eigenvalue Problems

The main result of this work is a Dancer-type bifurcation result for the quasilinear elliptic problem

Type II Codes over $$\mathbb{Z}/2k\mathbb{Z}$$, Invariant Rings and Theta Series

We consider type II codes over finite rings . It is well-known that their gth complete weight enumerator polynomials are invariant under the action of a certain finite subgroup of , which we denote H_k,g. We show that the invariant ring with respect to H_k,g is generated by such polynomials. This is carried out by using some closely related results concerning theta series and Siegel modular forms with respect to .     

Première valeur propre du laplacien, volume conforme et chirurgies

We define a new differential invariant a compact manifold by , where V _c (M, [g]) is the conformal volume of M for the conformal class [g], and prove that it is uniformly bounded above. The main motivation is that this bound provides a upper bound of the Friedlander-Nadirashvili invariant defined by . The proof relies on the study of the behaviour of when one performs surgeries on M.      

Vector optimization problems with quasiconvex constraints

Let X be a real linear space, a convex set, Y and Z topological real linear spaces. The constrained optimization problem min _C f(x), is considered, where f : X ₀→ Y and g : X ₀→ Z are given (nonsmooth) functions, and and are closed convex cones. The weakly efficient solutions (w-minimizers) of this problem are investigated. When g obeys quasiconvex properties, first-order necessary and first-order sufficient optimality conditions in terms of Dini directional derivatives are obtained. In the special case of problems with pseudoconvex data it is shown that these conditions characterize the global w-minimizers and generalize known results from convex vector programming. The obtained results are applied to the special case of problems with finite dimensional image spaces and ordering cones the positive orthants, in particular to scalar problems with quasiconvex constraints. It is shown, that the quasiconvexity of the constraints allows to formulate the optimality conditions using the more simple single valued Dini derivatives instead of the set valued ones.      

Probabilistic algorithm for finding roots of linearized polynomials

A probabilistic algorithm is presented for finding a basis of the root space of a linearized polynomial

On the discrepancy principle for some Newton type methods for solving nonlinear inverse problems

We consider the computation of stable approximations to the exact solution of nonlinear ill-posed inverse problems F(x) = y with nonlinear operators F : X → Y between two Hilbert spaces X and Y by the Newton type methods