FLQ, the Fastest Quadratic Complexity Bound on the Values of Positive Roots of Polynomials

In this paper we present F LQ, a quadratic complexity bound on the values of the positive roots of polynomials. This bound is an extension of FirstLambda, the corresponding linear complexity bound and, consequently, it is derived from Theorem 3 below. We have implemented FLQ in the Vincent-Akritas-Strzeboński Continued Fractions method (VAS-CF) for the isolation of real roots of polynomials and compared its behavior with that of the theoretically proven best bound, LM Q. Experimental results indicate that whereas F LQ runs on average faster (or quite faster) than LM Q, nonetheless the quality of the bounds computed by both is about the same; moreover, it was revealed that when VAS-CF is run on our benchmark polynomials using F LQ, LM Q and min(F LQ, LM Q) all three versions run equally well and, hence, it is inconclusive which one should be used in the VAS-CF method.

On the Exponential Bound of the Cutoff Resolvent

A simpler proof of a result of Burq [1] is presented.

An Improvement to the Achievement of the Griesmer Bound

We denoted by nq(k, d), the smallest value of n for which an [n, k, d]q code exists for given q, k, d. Since nq(k, d) = gq(k, d) for all d ≥ dk + 1 for q ≥ k ≥ 3, it is a natural question whether the Griesmer bound is attained or not for d = dk , where gq(k, d) = ∑[d/q^i], i=0,...,k-1, dk = (k − 2)q^(k−1) − (k − 1)q^(k−2). It was shown by Dodunekov [2] and Maruta [9], [10] that there is no [gq(k, dk ), k, dk ]q code for q ≥ k, k = 3, 4, 5 and for q ≥ 2k − 3, k ≥ 6. The purpose of this paper is to determine nq(k, d) for d = dk as nq(k, d) = gq(k, d) + 1 for q ≥ k with 3 ≤ k ≤ 8 except for (k, q) = (7, 7), (8, 8), (8, 9).

Note on an Improvement of the Griesmer Bound for q-ary Linear Codes

Let nq(k, d) denote the smallest value of n for which an [n, k, d]q code exists for given integers k and d with k ≥ 3, 1 ≤ d ≤ q^(k−1) and a prime or a prime power q. The purpose of this note is to show that there exists a series of the functions h3,q, h4,q, ..., hk,q such that nq(k, d) can be expressed.

New Upper Bound for the Edge Folkman Number Fe(3,5;13)

2000 Mathematics Subject Classification: 05C55.