Printer Friendly

On the minimal distance of a polynomial code.

1 Introduction

For two finite subsets of the positive integers, A and B let A * B = {ab | a [member of] A, b [member of] B and ab occurs odd many times in A * B}. In other words, if A = {[a.sub.1], ..., [a.sub.k]}, then A * B = [a.sub.1]B[DELTA] ... [DELTA][a.sub.k]B, where [DELTA] denotes the symmetric difference. For a positive integer m let m = {1, 2, ...,m}.

Conjecture 1 If n; k are positive integers, then |n * k| [greater than or equal to] n.

For an arbitrary finite subset A [subset] N it was proved that |m * A| [greater than or equal to] [pi](m) + 1, where [pi](x) is the prime counting function, and the following conjecture was formulated (Pilz (1992)):

Conjecture 2 Let n be a positive integer and K [subset] N be a finite set of integers. Then |n * K| [greater than or equal to] n.

These purely number theoretical problems originate in the theory of near-ring codes. A near-ring can be described as a ring, where the addition is not necessarily commutative and only one of the distributive laws is required. A typical example is the near-ring of polynomials, where the addition is the usual polynomial addition, and multiplication is the composition of the polynomials. In this example the addition is commutative and only the right distributive law holds. Near-rings play an important role in combinatorics: They are used to construct block designs that give rise to efficient error correcting codes. For more information on these codes see Eggetsberger (2011), Pilz (1983) and Pilz (2011). A special and very interesting near-ring code is defined in the following way: Let f 2 Z2[x] be a polynomial and C(f, k) the code generated (as a subspace) by the polynomials [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] a typical codeword is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where K is a finite subset of k. As C(f, k) is a linear code, its minimal distance is equal to the minimal weight of any nonzero codeword. Hence the minimum distance of C(f, k) is the minimal value of |n * K| for some K [subset or equal to] k.

In this paper we settle Conjecture 1, and prove that for arbitrary n [member of] N and finite set K [subset] N we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for some c > 0. Note that the minimal distance in C(f, k) depends heavily on f.

If, for example, we start with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] hence the minimal distance of the corresponding code is 2.

The natural logarithm will be denoted by log through the whole paper.

2 The general case

Let us denote by g(n) the minimal size of the set n * K, where K is a finite subset of the positive integers. In Pilz (1992) it is proved that g(n) [greater than or equal to] [pi](n) + 1. In this section we improve this lower bound and prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for some c > 0. The proof is based on the following lemma:

Proposition 1 For every positive integer n

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where the sum goes over the primes less than n, and [[alpha].sub.p] is the largest integer such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Proof: Let p [less than or equal to] n be a prime and [K.sub.p] [subset or equal to] the subset of K containing the elements that are divisible by the largest power of p occuring as divisor of some element of K (possibly [p.sup.0] = 1). Similarly, let [[??].sub.p] [subset or equal to] [??] be the set of elements of [??] that are divisible by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Note that [[??].sub.p] is never empty. By the maximality of the exponents of p in [K.sub.p] and [[??].sub.p], for any a [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] hold. We prove that for p < q [less than or equal to] n different primes [[??].sub.p] * [K.sub.p] and [[??].sub.q] * [K.sub.q] are disjoint. If for some a [member of] n and b [member of] K we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is in [??]. The exponent of p in [bar.a] is larger than the one in a, which is contradiction. Hence, [??] * K contains the disjoint union of the sets [[??].sub.p] * [K.sub.p] for p [less than or equal to] n, so

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

As [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Dividing by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] we obtain that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] thus by the definition of g we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

By (1) we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and this is what we wanted to prove.

Theorem 2 For every [lambda] > [[lambda].sub.0] there exists a c = c([lambda]) > 0 such that for every n > 1

g(n) [greater than or equal to] c * n /[log.sup.[lambda]] n,

where [[lambda].sub.0] satisfies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] Note that [[lambda].sub.0] ~ 0.223 ...

Proof: Fix 1 > [lambda] > [[lambda].sub.0]. We claim that there exists some c > 0 such that the inequality

g(n) [greater than or equal to] c * n /[log.sup.[lambda]] n (2)

holds for every n > 1. The proof is by induction on n. First we discuss the induction step. Assume that (2) holds for n < m. Now, we show that it holds for n = m, as well. The value of c will be chosen later. By Proposition 1 and the induction hypothesis:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (3)

In Rosser and Schoenfeld (1962) it is proved that [pi](m) < 1.25506 m/log m for every m > 1, hence [pi](m/2) - [pi]([square root of m]) [less than or equal to] [pi](m) < 1.5 * m/log m. For the second term of the last line of (3) we obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

since [lambda] < 1.

Now we estimate the main term. By Mertens' theorem, there exists a constant M such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

log log x + M + o(1). Hence, for every [epsilon] > 0 there exists B = B([epsilon]) such that for B [less than or equal to] a [less than or equal to] b

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (5)

holds. For m > [2.sup.2K] we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] < m/2. Applying (5) to the interval [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] where h is an integer satisfying 1 [less than or equal to] h [less than or equal to] K - 1 we obtain that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (6)

If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] Substituting into the main term of the last line of (3), omitting the integer parts and rearranging we get that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (7)

Now we show that there exists some K such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (8)

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] The sequence of functions [f.sub.K] converges to f. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

As 1 > [lambda] > [[lambda].sub.0], the Riemann-sum [T.sub.k] converges to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] converges to 0, it is easy to see that [S.sub.K] - [T.sub.K] converges to 0. Hence we can fix a K such that [S.sub.K] > 1. Now, we can choose some

[epsilon] > 0 such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

According to (4) there exists some R such that if R < m, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

By (3) and (7) we obtain that g(m) [greater than or equal to] c * m/[log.sup.[lambda]] m holds. If we choose c > 0 such that (2) holds for n [less than or equal to] max([2.sup.2K], [B.sup.2]([epsilon]), R), then (3) is gained.

3 The case K = [??]

In this section we prove Conjecture 1. We distinguish cases according to how large is k according to n. The conjecture is true for k [less than or equal to] 8. (Pilz (1992))

Case 1: 9 [less than or equal to] k [less than or equal to] 1.34 * log n

We show that in this case the number of elements that occur exactly once in the product [??] * [??] is at least n. We shall need the following two observations.

Lemma 3 Let n/2 < a [less than or equal to] n and b [member of] [??] such that a is relatively prime to every number less than k. Then ab occurs once in [??] * [??].

Proof: Let us assume that [a.sub.1], [a.sub.2] [member of] [??] and [b.sub.1], [b.sub.2] [member of] [??] satisfy the conditions of the lemma, and [a.sub.1][b.sub.1] = [a.sub.2][b.sub.2]. Now, [a.sub.1]|[a.sub.2][b.sub.2] and [a.sub.1] and [b.sub.2] are relatively prime, hence [a.sub.1]|[a.sub.2]. As [a.sub.1] > n/2 we have 2[a.sub.1] > n [greater than or equal to] [a.sub.2], thus [a.sub.1] = [a.sub.2], which implies [b.sub.1] = [b.sub.2].

Lemma 4 If k [greater than or equal to] 14, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] . Proof: In Rosser and Schoenfeld (1962) it is shown that for k > 1

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [gamma] is the Euler constant. For k > 21 by using the monotonicity of the logarithm function and [e.sup.-[gamma]] > 0.56 we get that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For 14 [greater than or equal to] k [greater than or equal to] 21 it is enough to check the statement when k = 14, 17 and 19. For these numbers the values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] are 0.506, 0.511 and 0.503, respectively, hence the statement holds.

Proposition 5 Let 9 [greater than or equal to] k [greater than or equal to] 1.34 * log n. Then |[??} * [??]| [greater than or equal to] n.

Proof: We show that there are at least n products satisfying the conditions of Lemma 3. For this we need to estimate the number of integers between n/2 and n that are not divisible by a prime less than k. This number will be denoted by D. By the inclusion-exclusion principle

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (9)

where [pi](k) = r and [p.sub.1], ..., [p.sub.r] are the primes up to k. Applying x - 1 < [x] [greater than or equal to] x to all [2.sup.r+1] terms of the right side we get that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (10)

If k [greater than or equal to] 14, Lemma 4 applies, and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

As k [less than or equal to] 1.34 log n, for k [greater than or equal to] 14 we have the estimation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Hence, D [greater than or equal to] 0.24n/log k. Using Lemma 3 we obtain |[??] * [??]| [greater than or equal to] Dk. The function x/log x is monotone increasing on [1, [infinity]), thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For 9 [less than or equal to] k [less than or equal to] 13 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For 10 [less than or equal to] k [less than or equal to] 13 it is obtained by calculation that the right hand side is greater than n if n [greater than or equal to] [e.sup.k/1.34]. For k = 9 the inequality holds if n > 5040. By brute force the statement can be checked for k = 9 and n [less than or equal to] 5040. Thus we obtained |[??] * [??]| > n.

Case 2: 1.34 * log n [less than or equal to] k [less than or equal to] n - 0.22 * n/log n and n [greater than or equal to] 1410.

Let [k.sub.1] = max(k; n/7) and [k.sub.1] < p [less than or equal to] n a prime. As k < p, the set of elements of [??] * [??], which are divisible by p is {p, 2p, ..., [n/p]p} * [??]. This set has the same cardinality as the set [n/p] * [??]. Now, [n/p] [less than or equal to] 6, hence [n/p] * [??]| [greater than or equal to] k. It is easy to see that for p > q > n/7 an element of [??] * [??] cannot be divisible by both p and q. Hence, |[??] * [??]| [greater than or equal to] ([pi](n) - [pi]([k.sub.1]))k.

At first, suppose that k [less than or equal to] n/7. By a theorem of Dusart Dusart (1999) for x [greater than or equal to] 17

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

holds. Hence, [pi](n) - [pi](n/7) [greater than or equal to] 0.749 * n/log n for n [greater than or equal to] 1410. As 1.34 * log n [less than or equal to] k, we have

|[??] * [??]| [greater than or equal to] 1.34 * 0.749 * n > n.

Secondly, let us consider the case when n/7 < k [less than or equal to] n/2. As [pi](n) - [pi](n/2) [greater than or equal to] 7,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Finally, let n/2 < k < n 0.22 * n/ log n. Then by the estimates in Dusart (1999) and Robin (1983) there are at least two primes between k and n if n > 90000. It can be checked that this also holds for n > 1410. Thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

We continue with the case when k is "large", that is, n 0.4 * n /log n+1.02 [less than or equal to] k. By calculation we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Case 3:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

If k = n, then [??] * [??] = {1, ..., n} * {1, ..., n}. If a [not equal to] b, then pairing ab with ba only the products of the form a * a are left, hence [??] * [??] = {[1.sup.2], [2.sup.2], ..., [n.sup.2]}. Thus

|[??] * [??]| = n.

Assume now that k < n. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (11)

For the first term on the right side of (11) we have

|[??] * [??]| = {[1.sup.2], [2.sup.2], ..., [k.sup.2]}| = k. (12)

Lemma 6 For the second term of (11) we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (13)

Proof: We use the following observation: If

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

then ij appears exactly once in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Let us assume that ij = i'j' such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] Now, changing the roles of (i, j) and (i', j') we may assume that i < i'. As ij = i'j', we have i/i' = j'/j and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which is a contradiction. For ([??] \ [??]) * [??] we obtain that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (14)

Now, we focus on the third term of (11).

Lemma 7 For the third second term of (11)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (15)

holds.

Proof: It is enough to show that among the numbers [1.sup.2], [2.sup.2], ..., [k.sup.2] at most 0.431k many has a divisor in the interval [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is the largest square divisor of m. Since [a.sub.m] is squarefree, m|[i.sup.2] if and only if [a.sub.m][b.sub.m]|i. Let S denote the following upper bound of the number of elements of the set {[1.sup.2], [2.sup.2], ..., [k.sup.2]} which have a divisor in [k + 1, n]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Recall that m = [a.sub.m][b.sup.2.sub.m], where [a.sub.m] is squarefree. Now, summing by j = [b.sub.m] [less than or equal to] [square root of m]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Rewrite S = k([S.sub.1] + [S.sub.2]), where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

First, we give an upper bound for [S.sub.1].

Lemma 8

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (16)

Proof: [r.sub.j] = [k + 1/[j.sup.2]] and [s.sub.j] = [n/[j.sup.2]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (17)

The function 1/x is a nonnegative decreasing function on (0, [infinity]), hence we can estimate the inside sum by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Substituting into (17) we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (18)

Since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (19)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (20)

from the inequalities (18), (19), (20) we get (16).

Now we give an upper bound for [S.sub.2]

Lemma 9

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (21)

Proof:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (22)

In (22) for every j we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Hence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for m = i[j.sup.2] (i = 1, 2, 3) we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For fixed i, the number of j such that m = i[j.sup.2] is at most:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and this is what we wanted to show. 2

Summarizing the results, from (16) and (21) we obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (23)

We assumed that n 0.4*n/log n+1.02 [less than or equal to] k and n [greater than or equal to] 5000. By using the inequality [e.sup.-x] < 1/1+x we obtain that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] we have that k/n > 0.958.

By easy calculation from these inequalities the following ones can be deduced:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (24)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (25)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (26)

Adding (24), (25) and (26) using (23) we arrive at:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (27)

Then from inequalities (12), (13) and (15) in case k/n > 0.958 we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

thus we proved the statement in Case 3 as well.

We proved the statement for all pairs n, k where n [greater than or equal to] 5000. Cases k [less than or equal to] n [less than or equal to] 5000 can be checked by brute force.

received 28th April 2010, revised 16th March 2011, accepted 17th March 2011.

References

P. Dusart. The kth prime is greater than k(ln k + ln ln k - 1) for k [greater than or equal to] 2. Math. Comp., 68(225):411-415, 1999.

R. Eggetsberger. On constructing codes from planar nearrings. http://www.algebra.uni-linz. ac.at/Nearrings/nrcodes.html, 2011.

G. Pilz. Near-rings, volume 23 of North-Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam, second edition, 1983. ISBN 0-7204-0566-1. The theory and its applications.

G. Pilz. On polynomial near-ring codes. In Contributions to general algebra, 8 (Linz, 1991), pages 233-238. Holder-Pichler-Tempsky, Vienna, 1992.

G. Pilz. Near-rings: What they are and what they are good for. http://www.algebra.uni-linz. ac.at/Nearrings/what-are.html, 2011.

G. Robin. Estimation de la fonction de Tchebychef [theta] sur le k-ieme nombre premier et grandes valeurs de la fonction [omega](n) nombre de diviseurs premiers de n. Acta Arith., 42(4):367-389, 1983.

J. B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois J. Math., 6:64-94, 1962.

Peter Pal Pach ([dagger]) and Csaba Szabo ([double dagger])

Eotvos Lorand University, Department of Algebra and Number Theory, Budapest, Hungary

([dagger]) Email: ppp24@cs.elte.hu

([double dagger]) Email: csaba@cs.elte.hu
COPYRIGHT 2011 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Pach, Peter Pal; Szabo, Csaba
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:4EXHU
Date:Dec 1, 2011
Words:3330
Previous Article:The extended equivalence and equation solvability problems for groups.
Next Article:On the residual solvability of generalized free products of solvable groups.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters