Bounds for traces in complete intersections and degrees in the Nullstellensatz

In this paper we obtain an effective Nullstellensatz using quantitative considerations of the classical duality theory in complete intersections. Letk be an infinite perfect field and let f₁,...,f n–rk[X₁,...,X_n] be a regular sequence with d:=max_j deg f_j. Denote byA the polynomial ringk [X₁,..., X_r] and byB the factor ring k[X₁,...,X_n]/(f₁,...,f_n r); assume that the canonical morphism AB is injective and integral and that the Jacobian determinant with respect to the variables X_r+1,...,X_n is not a zero divisor inB. Let finally B^*:=Hom_A(B, A) be the generator of B^* associated to the regular sequence.We show that for each polynomialf the inequality deg (¯f) dⁿ r(+1) holds (¯fdenotes the class off inB and is an upper bound for (n–r)d and degf). For the usual trace associated to the (free) extensionA B we obtain a somewhat more precise bound: deg Tr(¯f) dⁿ r degf. From these bounds and Bertini's theorem we deduce an elementary proof of the following effective Nullstellensatz: let f₁,..., f_s be polynomials in k[X₁,...,X_n] with degrees bounded by a constant d2; then 1 (f₁,..., f_s) if and only if there exist polynomials p₁,..., p_sk[X₁,..., X_n] with degrees bounded by 4n(d+ 1)ⁿ such that 1=_ip_if_i. in the particular cases when the characteristic of the base fieldk is zero ord=2 the sharper bound 4ndⁿ is obtained.Partially supported by UBACYT and CONICET (Argentina)     

A Resultant Theory for the Systems of Two Ordinary Algebraic Differential Equations

 A notion of resultant in determinantal form of two ordinary algebraic differential equations is introduced and some properties are shown. This notion extends the analogous one given in the linear homogeneous case by Berkovich and Tsirulik in 1986 and it can be used for the elimination of variables and their derivatives. Received: September 29, 1995; revised version: August 2, 1996/January 4, 1997     

Bounds on the Weight Hierarchies of Extremal Non-chain Codes of Dimension 4

 The weight hierarchy of a linear [n, k; q] code C over GF(q) is the sequence (d ₁, d ₂, . . . , d _k ) where d _r is the smallest support of an r-dimensional subcode of C. An [n, k; q] code is external non-chain if for any r and s, where 1≦r<s≦k, there are no subspaces D and E, such that D⊂E, dim D=r, dim E=s, w _S (D)=d _r , and w _S (E)=d _s . Bounds on the weight hierarchies of such codes of dimension 4 are studied. Received: September 27, 1996     

The Matroid of Supports of A Linear Code

 A relation between the Hamming weight enumerator of a linear code and the Tutte polynomial of the corresponding matroid has been known since long ago. It provides a simple proof of the MacWilliams equation (see D. Welsh, Matroid Theory (1976)). In this paper we prove analogous results for the support weight distributions of a code. Received March 5, 1996; revised version October 28, 1996     

On the Covering Radius of Long 5-ary BCH Codes with Minimum Distance 7

 We study S. D. Cohen’s method of estimating the covering radius of long primitive non-binary BCH codes with prime field alphabet. As an application we show that the covering radius is at most 7 for long 5-ary BCH codes with minimum distance seven. Received: November 13, 1996; revised version: March 11, 1997     

On the Uniformity of Distribution of the ElGamal Signature

 We show that, under some natural conditions,the pairs (r,s) produced by the ElGamal signature scheme are uniformly distributed. In particular this implies that values of r and s are not correlated. The result is based on some new estimates of exponential sums. Received: May 17, 2000; revised version: August 23, 2001     

On the Number of Special Permutation-Invariant Orbits and Terms

 This note presents a lower and an upper bound for the cardinality of the set of special permutation-invariant orbits and a formula for the number of special terms. Received: August 24, 1994; revised version: October 17, 1996/March 21, 1997     

On New Perfect Binary Nonlinear Codes

 We present a new construction of binary nonlinear perfect codes with minimum distance 3 and lowerbound the number of nonequivalent such codes. Received: November 26, 1996; revised version: March 14, 1997     

An Elementary Proof to the Weight Distribution Formula of the First Order Shortened Reed-Muller Coset Code

 Let RM(m, r) be the shortened Reed-Muller code of order r and of length 2 ^m −1. A simple proof to the Kasami’s weight distribution formula (see [2] and [3, p. 441]) of the cosets of RM(m, 1) in RM(m, 2) is given. The derivation of this distribution formula (21) is based only on elementary properties of the trace map and the Dickson theory of quadratic forms (see [1, pp. 197–199] and [3, pp. 434–442]) is no longer needed. Received: September 25, 1996; revised version: March 11, 1997     

F-partitions of Cyclic Groups

 An F-partition is a partition of an abelian group with the property that the linear space generated by the indicator functions of the subsets in the partition is invariant under Fourier transformation. In the present paper we study the special case of F-partitions over cyclic groups. We introduce the concept of multiplicative partitions and we show that for cyclic groups of prime orders any F-partition is necessarily multiplicative. Received: October, 1996; revised version: March 17, 1997     

On Covering Radius and Discrete Chebyshev Polynomials

 We derive a new upper bound on the covering radius of a code as a function of its dual distance. This bound improves on the Honkala-Litsyn-Tiet?v?inen bound and in a certain interval it is also better than Tiet?v?inen’s bound. Upper bounds on even-weight codes are considered as well. Received: November 4, 1996; revised version: February 1, 1997     

On Generalized Fibonacci Cubes and Unitary Transforms

 We present a new interconnection topology called generalized Fibonacci topology, which unifies a wide range of connection topologies such as the Boolean cube (or hypercube), classical Fibonacci cube, etc. Some basic topological properties of generalized Fibonacci cubes are established. Finally, we developed new classes of the discrete orthogonal transforms, based on the generalized Fibonacci recursions. They can be implemented efficiently by butterfly-type networks (like the Fourier, or the Haar transforms). A generalized Fibonacci cube based processor architecture (generalizing the known SIMD architecture — hypercube processor) can be efficiently used for hardware implementation of the proposed discrete orthogonal transforms. Received: October 31, 1996     

Minimal Primary Decomposition and Factorized Gröbner Bases

 This paper continues our study of applications of factorized Gr?bner basis computations in [8] and [9]. We describe a way to interweave factorized Gr?bner bases and the ideas in [5] that leads to a significant speed up in the computation of isolated primes for well splitting examples. Based on that observation we generalize the algorithm presented in [22] to the computation of primary decompositions for modules. It rests on an ideal separation argument. We also discuss the practically important question how to extract a minimal primary decomposition, neither addressed in [5] nor in [17]. For that purpose we outline a method to detect necessary embedded primes in the output collection of our algorithm, similar to [22, cor. 2.22]. The algorithms are partly implemented in version 2.2.1 of our REDUCE package CALI [7]. Received: September 29, 1995; revised version: May 23, 1996     

Constraints on Weights in Binary Codes

 There are known constraints on the number of doubly-even and singly-even vectors in a linear even binary code C. These constraints give information about C∩C ^⊥. We find new constraints on weights in a binary linear code C which also contains odd weight vectors. This leads to information about the dimension and weights of C∩C ^⊥. Received: September 20, 1996     

The Discrete Fourier Transform of a Recurrent Sequence

 We prove a theorem of H. A. Barker on the Fourier coefficients of the sequence obtained by applying a complex-valued function to a recurrent sequence over a finite field. It is shown to follow from a result on the modulus of certain character sums which are evaluated in terms of Gauss sums. Received: April 1, 1997; revised version: August 29, 1997     

An Inequality About the Largest Roots of a Polynomial

 We present an upper bound for the product of the k largest roots of a monic polynomial of degree n with complex coefficients. For that, we use the theory of compound matrices and the localization of the eigenvalues of matrices. Received: February 26, 1996; revised version: March 20, 1997     

On extreme values of orbit lengths in M/G/1 queues with constant retrial rate

In the design of waiting facilities for the units in a retrial queue, it is of interest to know probability distributions of extreme values of the orbit length. The purpose of this paper is to investigate the asymptotic behavior of the maximum orbit length in the queue with constant retrial rate, as the time interval increases. From the classical extreme value theory, we observe that, under standard linear normalizations, the maximum orbit length up to the nth time the positive recurrent queue becomes empty does not have a limit distribution. However, by allowing the parameters to vary with n, we prove the convergence of maximum orbit lengths to three possible limit distributions when the traffic intensity approaches 1 from below and n approaches infinity.

---

---

Received: October 7, 1999 / Accepted: November 21, 2000     

Weight Distribution of the Hermitian Forms Codes

 We recall the construction of the hermitian-forms codes and some results about hermitians forms and exponential sums. With the help of these results, we give the weight distribution of the hermitian-forms codes and give some examples for which experimental computations have been made. Received: September 8, 1993; revised version: October 4, 1995     

Safe Operators: Brackets Closed Forever Optimizing Optimal λ-Calculus Implementations

 Considerations from category theory described in [1] have permitted to add new rewriting rules for optimal reductions of the λ-calculus [19, 14]. These rules produce an impressive improvement in the performance of the reduction system, and provide a first step towards the solution of the well known and crucial problem of accumulation of control operators. In this paper, after an introduction to optimal reductions, we exhibit the aforementioned problem and prove the correctness of the new rules. Received August 28, 1995; revised version August 1, 1996     

Cryptanalysis of ‘Less Short’ RSA Secret Exponents

 In some applications of RSA, it is desirable to have a short secret exponent d. Wiener [6], describes a technique to use continued fractions (CF) in a cryptanalytic attack on an RSA cryptosystem having a ‘short’ secret exponent. Let n=p ⋅ q be the modulus of the system. In the typical case that G=gcd(p−1, q−1) is small. Wiener’s method will give the secret exponent d when d does not exceed (approximately) n ^1/4. Here, we describe a general method to compute the CF-convergents of the continued fraction expansion of the same number as in Wiener (which has denominator d ⋅ G) up to the point where the denominator of the CF-convergent exceeds approximately n ^1/4. When d<n ^1/4 this technique determines d, p, and q as does Wiener’s method. For larger values of d there is still information available on the secret key. An estimate is made of the remaining workload to determine d, p and q. Roughly speaking this workload corresponds to an exhaustive search for about 2r+8 bit, where r=ln₂ d/n ^1/4. Received: September 30, 1996; revised version: March 7, 1997