ON THE CASTELNUOVO-MUMFORD REGULARITY OF A PROJECTIVE SYSTEM

Martin Kreuzer Rolf Waldi

Fakultät für Mathematik Universität Regensburg D-93040 Regensburg, Germany

1. Introduction

Let ℙ^{N}(𝔽_{q}) be the projective space of dimension N ≥ 1 over a field of q = p^{e} elements (p prime, e ≥ 1). Using the terminology of [12], a projective [n, k + 1]_{q}-system is a subset 𝕏 ⊆ ℙ^{N}(𝔽_{q}) consisting of n ≥ 2 points and spanning a linear subspace of dimension k ≥ 1. We denote by H_{𝕏} : ℤ ⟶ ℕ the Hilbert function of 𝕏, and by ΔH_{𝕏} its first difference function which is also called the Castelnuovo function of 𝕏. Although the description of the possible Hilbert functions of finite subsets of the projective space ℙ^{N}(\overline{𝔽}_{q}) over the algebraic closure \overline{𝔽}_{q} of 𝔽_{q} is well-known, no such result seems to be available for projective [n, k + 1]_{q}-systems. The present paper is intended as a first step in that direction.

In the above situation, the Castelnuovo-Mumford regularity r_{𝕏} of the ideal of 𝕏 in ℙ_{𝔽_{q}}^{N} is given by r_{𝕏} = max{ν ∈ ℤ | ΔH_{𝕏}(ν) ≠ 0}. Considering the fact that 𝕏 is a subset of the very special set of 𝔽_{q}-rational points of ℙ_{𝔽_{q}}^{N}, we are interested in finding the possible values of r_{𝕏} in terms of the number of points n and their embedding dimension k. Notice that we trivially have 1 ≤ k < n ≤ \frac{q^{k+1}−1}{q−1}. Specifically, we want to study the functions

s(n, k, q) = sup{r_{𝕏} | 𝕏 ⊆ ℙ^{k}(𝔽_{q}) projective [n, k + 1]_{q}-system }  and
s(n, q) = sup\{s(n, k, q) | 1 ≤ k < n ≤ \frac{q^{k+1}−1}{q−1}\}

= sup{r_{𝕏} | 𝕏 ⊆ ℙ^{k}(𝔽_{q}) projective [n, k + 1]_{q}-system for some k ≥ 1}.

Geometrically, we can interpret s(n, q) as the least number s such that, for every set of 𝔽_{q}-rational points {P_{1}, …, P_{n}} in some projective space over 𝔽_{q}, there exists a hypersurface of degree s containing P_{1}, …, P_{n−1}, but not P_{n} (cf. [4]). Once we know s(n, k, q), we can determine all possible values of r_{𝕏} as follows.

1.1. Proposition. Let σ(n, k, q) be the largest integer σ such that n > H_{ℙ^{k}(𝔽_{q})}(σ), where the value of that Hilbert function is given by [11], Thm. 1. Then the Castelnuovo-Mumford regularity r_{𝕏} of a projective [n, k+1]_{q}-system 𝕏 ⊆ ℙ^{N}(𝔽_{q}) satisfies σ(n, k, q) ≤ r_{𝕏} ≤ s(n, k, q), and every value of r_{𝕏} between those bounds is attained.

Using the language of Boolean algebra, Renate Beinhauer proved in [1] that, for all n ≥ 2, we have s(n, 2) = ⌊log_{2}(n + 1)⌋. Here ⌊x⌋ denotes the largest integer smaller than or equal to a real number x. Another proof of this result can be derived from standard facts about binary Reed-Muller codes (cf. [10], sec. 4.5). In this paper, we shall show the following generalization.

1.2. Proposition. Let k ≥ 1 and k + 1 ≤ n ≤ 2^{k+1} − 1. Then s(n, k, 2) + 1 is the uniquely determined number l such that 2^{l−1} − l + 1 ≤ n − k < 2^{l} − l. In particular, the invariant s(n, k, 2) depends only on n − k and satisfies s(2^{k+1} − 1, k, 2) = k + 1.

In case q ≥ 3, the authors have not been able to determine s(n, k, q) and s(n, q) completely. However, it is possible to show the following bound for s(n, q).

1.3. Proposition. For n ≥ 2 choose m ≥ 1 such that \frac{q^{m}−1}{q−1} ≤ n < \frac{q^{m+1}−1}{q−1}. Then we have

s(n, q) ≥ (m − 1)(q − 1) + 1

with equality in case q = 2.

If we take three collinear points in ℙ^{N}(𝔽_{3}), we see that s(3, 3) ≥ 2. Thus the bound of 1.3 is not sharp for q ≥ 3. At the beginning and the end of the range k < n ≤ \frac{q^{k+1}−1}{q−1}, the invariant s(n, k, q) can be computed explicitly.

1.4. Proposition. a) For k < n ≤ q + k we have s(n, k, q) = n − k. b) For q + k ≤ n < 2q + k we have s(n, k, q) = q.

c) For 2q + k ≤ n ≤ q^{k} we have s(n − 1, k, q) ≤ s(n, k, q) ≤ \frac{1}{2}(n + 2 − k).

d) For q^{k} ≤ n < \frac{q^{k+1}−1}{q−1} we have s(n, k, q) = k(q − 1).

e) For n = \frac{q^{k+1}−1}{q−1} we have s(n, k, q) = k(q − 1) + 1.

Consequently, we obtain a number of values and estimates for s(n, q).

1.5. Corollary. a) For 2 ≤ n ≤ q + 1 we have s(n, q) = n − 1.

b) For q + 1 ≤ n ≤ 2q + 1 we have s(n, q) = q.

c) For n ≥ 2q + 2 we have s(n, q) ≤ \frac{q−1}{2q−1}(n + 2).

In view of 1.2, 1.3, and 1.5, one may ask how s(n, q) grows asymptotically. It appears natural to conjecture that lim_{n→∞} \frac{s(n,q)}{log n} = \frac{q−1}{log q}.

There is one more situation in which we can determine the invariants s(n, k, q) completely, namely for k ≤ 2. We remark that for k = 1 a projective system 𝕏 has r_{𝕏} = n − 1. Therefore we get s(n, 1, q) = n − 1 for n = 2, …, q + 1. Based on some results of E. Davis (cf. [3]) about geometrical properties of sets of points in ℙ^{2}, we can also find all numbers s(n, 2, q). The following proposition was first found by experimental calculation using the computer algebra system CoCoA (cf. [2]).

1.6. Proposition. a) For 3 ≤ n ≤ q + 2 we have s(n, 2, q) = n − 2. b) For q + 2 ≤ n ≤ 3q − 1 we have s(n, 2, q) = q.

c) For 3q ≤ n < q^{2} we choose ν ∈ {3, …, q − 1} such that νq ≤ n < (ν + 1)q. Then we have s(n, 2, q) = q + ν − 2.

d) For q^{2} ≤ n ≤ q^{2} + q we have s(n, 2, q) = 2q − 2.

e) For n = q^{2} + q + 1 we have s(n, 2, q) = 2q − 1. In this case, the projective system 𝕏 equals ℙ^{2}(𝔽_{q}) and has Castelnuovo function ΔH_{𝕏} : 1 2 ⋯ (q + 1) (q − 1) (q − 2) ⋯ 2 1.

In order to prove the above propositions, we shall recall some facts about 0-dimensional subschemes of ℙ_{𝔽_{q}}^{N} in the next section. In the last part of this paper we explain other motivations for studying the numbers s(n, k, q) and s(n, q) and provide interpretations and applications in coding theory, local algebra, and set theory.

2. Castelnuovo functions of projective systems

In this section we let 𝕏 ⊆ ℙ^{N}(𝔽_{q}) be a projective [n, k + 1]_{q}-system. Since we are mainly interested in H_{𝕏} and ΔH_{𝕏}, we may assume N = k. The homogeneous coordinate ring of ℙ_{𝔽_{q}}^{k} is 𝔽_{q}[X_{0}, …, X_{k}], and the homogeneous vanishing ideal of 𝕏 will be denoted by I_{𝕏}. We start by listing some basic properties of ΔH_{𝕏} (cf. [3], [4], [5]).

2.1. Proposition. a) For i ∈ ℤ we have ΔH_{𝕏}(i) ≠ 0 if and only if 0 ≤ i ≤ r_{𝕏}.

b) We have ΔH_{𝕏}(0) = 1 ≤ ΔH_{𝕏}(1) = k and ∑_{i=0}^{r_{𝕏}} ΔH_{𝕏}(i) = n.

c) If ΔH_{𝕏}(i) = 1 for some i ≥ 1, then ΔH_{𝕏}(j) = 1 for all i ≤ j ≤ r_{𝕏}.

d) If ΔH_{𝕏}(r_{𝕏} − 1) = ΔH_{𝕏}(r_{𝕏}) = 1, then there exists a line in ℙ^{k}(𝔽_{q}) containing at least r_{𝕏} + 1 points of 𝕏 (cf. [5], 5.2).

e) For every subset 𝕐 ⊆ 𝕏 we have ΔH_{𝕐} ≤ ΔH_{𝕏} and r_{𝕐} ≤ r_{𝕏}. If #𝕐 = n − 1, then we also have r_{𝕏} ≤ r_{𝕐} + 1.

f) For every s ∈ {1, …, n} there exists a subset 𝕐 ⊆ 𝕏 consisting of s points such that H_{𝕐} = min{s, H_{𝕏}} (cf. [4], 1.14 or [5], 2.5.c).

2.2. Corollary. a) The function s(n, k, q) is monotonically increasing in n.

b) For k < n ≤ \frac{q^{k+1}−1}{q−1} we have s(n, k, q) ≤ s(n + 1, k + 1, q) and s(n, k, q) ≤ n − k. In particular, we have s(n, q) ≤ s(n + 1, q).

Proof: Claim a) follows from 2.1.e. If we take a projective [n, k + 1]_{q}-system 𝕏 ⊆ ℙ^{k}(𝔽_{q}) such that r_{𝕏} = s(n, k, q) and embed ℙ^{k}(𝔽_{q}) ⟶ ℙ^{k+1}(𝔽_{q}) by (x_{0} : …: x_{k}) ⟼ (0 : x_{0} : …: x_{k}), we can add the point (1 : 0 : …: 0) to 𝕏 and obtain a new set 𝕐 ⊆ ℙ^{k+1}(𝔽_{q}) whose Castelnuovo function differs by 2.1.b from ΔH_{𝕏} only at ΔH_{𝕐}(1) = k + 1 = ΔH_{𝕏}(1) + 1. Thus the first inequality of b) follows from 2.1.e. The second inequality follows from 2.1.a and 2.1.b, because ΔH_{𝕏} : 1 k (≥ 1) ⋯ (≥ 1) adds up to n ≥ r_{𝕏} + k. □

Other ingredients we need are the basic properties of the projective systems ℙ^{k}(𝔽_{q}) and 𝔸^{k}(𝔽_{q}). Here we embed 𝔸^{k}(𝔽_{q}) ⟶ ℙ^{k}(𝔽_{q}) by mapping (x_{1}, …, x_{k}) to (1 : x_{1} : …: x_{k}). The following proposition follows from [9] and [11].

2.3. Proposition. a) For 𝕏 = ℙ^{k}(𝔽_{q}) we have r_{𝕏} = k(q − 1) + 1. The ideal

I_{𝕏} is generated by the 2 × 2-minors of the matrix ( \begin{matrix}X_{0}^{q} & ⋯ & X_{k}^{q} \\ X_{0} & ⋯ & X_{k} \end{matrix} ). The set 𝕏 is a Cayley-Bacharach scheme such that r_{𝕏\{P }} = r_{𝕏} − 1 for all P ∈ 𝕏.

b) The set 𝕐 = 𝔸^{k}(𝔽_{q}) ⊆ ℙ^{k}(𝔽_{q}) is a projective [q^{k}, k + 1]_{q}-system with r_{𝕐} = k(q − 1). The ideal I_{𝕐} is generated by the regular sequence (X_{1}^{q} − X_{0}^{q−1}X_{1}, …, X_{k}^{q} − X_{0}^{q−1}X_{k}). Also the set 𝕐 is a Cayley-Bacharach scheme such that r_{𝕐\{P }} = r_{𝕐} − 1 for all P ∈ 𝕐.

Proof: The Hilbert functions of 𝕏 and 𝕐 were computed in [11]. By localizing in X_{i}, one may check that the ideal of 2 × 2-minors in a) defines 𝕏 settheoretically. Since it is determinantal, it is also saturated and therefore the homogeneous vanishing ideal of 𝕏. Now [9], 3.6 shows the remaining claim of a). Since the sequence in b) obviously defines 𝕐 set-theoretically and is a regular sequence, it generates I_{𝕐}. The fact that complete intersections are Cayley-Bacharach schemes is well-known. □

Now we are ready to start proving the results announced in section 1.

Proof of Proposition 1.1: For every projective [n, k + 1]_{q}-system 𝕏 ⊆ ℙ^{k}(𝔽_{q}), there exists a point P ∈ 𝕏 such that the Castelnuovo funcion of 𝕐 = 𝕏 \ {P } differs from ΔH_{𝕏} only at ΔH_{𝕐}(r_{𝕏}) = ΔH_{𝕏}(r_{𝕏}) − 1 (cf. 2.1.f). Since at least one of the points of ℙ^{k}(𝔽_{q}) \ 𝕐 is not a common zero of the polynomials in (I_{𝕐})_{α_{𝕐}}, where α_{𝕐} = min{i ∈ ℕ | (I_{𝕐})_{i} ≠ 0}, we can add a point Q of ℙ^{k}(𝔽_{q}) to 𝕐 such that the Castelnuovo function of 𝕐 ∪ {Q} differs from ΔH_{𝕐} only at ΔH_{𝕐∪{Q}}(α_{𝕐}) = ΔH_{𝕐}(α_{𝕐}) + 1. Continuing this way, we can replace one point after another, while decreasing the Castelnuovo function at the end and increasing it at the first point where it differs from the Castelnuovo function of ℙ^{k}(𝔽_{q}). If we start with a projective [n, k + 1]_{q}-system 𝕏 with r_{𝕏} = s(n, k, q), we can thus produce every Castelnuovo-Mumford regularity going down from s(n, k, q) to the regularity σ(n, k, q) of a subset of ℙ^{k}(𝔽_{q}) whose Hilbert function agrees with H_{ℙ^{k}(𝔽_{q})} as long as possible. □

Proof of Proposition 1.3: From 2.2 and 2.3.a we obtain the chain of inequalities s(n, q) ≥ s(\frac{q^{m}−1}{q−1}, q) ≥ s(\frac{q^{m}−1}{q−1}, m − 1, q) = (m − 1)(q − 1) + 1. □

Proof of Proposition 1.4: To prove claim a), we note that s(n, k, q) ≤ n − k and s(n, k, q) ≥ s(n − k + 1, 1, q) = n − k by 2.2.b. Now let 𝕏 be a projective [n, k + 1]_{q}-system. To prove b) for n > q + k ≥ q + 1, we distinguish two cases. If ΔH_{𝕏}(r_{𝕏} − 1) > 1, then 2.1.c yields a Castelnuovo function of the form ΔH_{𝕏} : 1 k (≥ 2) ⋯ (≥ 2) (≥ 1) which sums up to n ≥ 2r_{𝕏} + k − 2. In this case we get r_{𝕏} ≤ \frac{1}{2}(n + 2 − k) < q + 1, and the monotonicity of s(n, k, q) together with a) finishes the proof. On the other hand, if ΔH_{𝕏}(r_{𝕏} − 1) = 1, then we have by 2.1.c and 2.1.d at least r_{𝕏} + 1 points of 𝕏 on a line. Thus we get r_{𝕏} + 1 ≤ q + 1 in this case, too.

The first inequality of c) is a special case of 2.2.a. The second inequality follows from ΔH_{𝕏}(r_{𝕏} −1) > 1 (cf. 2.1.c) and the above summation argument. Since e) is a consequence of 2.3.a, we are left with proving d). From the last statement of 2.3.a we get s(n, k, q) ≤ k(q − 1). But 2.3.b shows s(q^{k}, k, q) ≥ k(q − 1), so that another application of 2.2.a finishes the proof. □

Proof of Corollary 1.5: Claim a) follows from 1.4.a. For q + 2 ≤ n ≤ 2q + 1 we have s(n, q) ≥ s(q + 1, q) = q by a). Now we choose k ≥ 2 such that s(n, q) = s(n, k, q). Notice that k = 1 is not possible here, because n ≥ q + 2 and #ℙ^{1}(𝔽_{q}) = q + 1. Then we have n ≤ 2q + 1 < 2q + k, and 1.4.b yields s(n, q) = s(n, k, q) ≤ s(2q + k − 1, q) = q. Altogether, we find s(n, q) = q, as claimed in b).

Finally we prove c). Let n ≥ 2q + 2, let 𝕏 be a projective [n, k + 1]_{q}- system, and choose m ≥ 1 such that \frac{q^{m}−1}{q−1} ≤ n < \frac{q^{m+1}−1}{q−1}. Notice that this implies 2 ≤ m ≤ k + 1. We distinguish two cases. In case m = k + 1, we have n = \frac{q^{k+1}−1}{q−1} and r_{𝕏} = k(q − 1) + 1 = (m − 1)(q − 1) + 1 by 2.3.a. Since n = \frac{q^{m}−1}{q−1} ≥ 2q + 2 and q ≥ 2, it easily follows that (m − 1)(q − 1) + 1 ≤ (n + 2)\frac{q−1}{2q−1}.

It remains to consider the case 2 ≤ m ≤ k. Since q ≤ (n + 2)\frac{q−1}{2q−1}, it suffices to show r_{𝕏} ≤ (n + 2)\frac{q−1}{2q−1} for r_{𝕏} ≥ q + 1. From 2.3.a and n < \frac{q^{k+1}−1}{q−1}, we get r_{𝕏} ≤ k(q − 1). Since r_{𝕏} ≥ q + 1, we conclude n ≥ 2q + k from 1.4.b. By 1.4.c, we then have r_{𝕏} ≤ \frac{1}{2}(n + 2 − k), and altogether we arrive at r_{𝕏} ≤ min\{k(q − 1), \frac{1}{2}(n + 2 − k)\} ≤ (n + 2)\frac{q−1}{2q−1}. □

Before we proceed to prove 1.2, we need some preparations. We denote the homogeneous coordinate ring of 𝕏 by R = 𝔽_{q}[X_{0}, …, X_{k}]/I_{𝕏}. It is a standard graded 𝔽_{q}-algebra, i.e. we have R = ⊕_{i≥0}R_{i} with R_{0} = 𝔽_{q}, with dim_{𝔽_{q}}(R_{1}) < ∞, and with R = 𝔽_{q}[R_{1}]. We let 𝕏 = {P_{1}, …, P_{n}} and choose homogeneous coordinates P = (p_{i0}, …, p_{ik}) for i = 1, …, n. The following result follows from [6].

2.4. Proposition. a) For each n ≥ 0, there exists an injective 𝔽_{q}-linear map ı_{n} : R_{n} ⟶ 𝔽_{q}^{n} given by ı_{n}(r) = (r(p_{10}, …, p_{1k}), …, r(p_{n0}, …, p_{nk})).

b) For all i ≥ 0, we have H_{𝕏}(i) = dim_{𝔽_{q}}(R_{i}) = dim_{𝔽_{q}} ı_{i}(R_{i}).

c) If q = 2, the images of the maps ı_{n} form an increasing sequence of 𝔽_{2}-vector spaces ı_{1}(R_{1}) ⊆ ı_{2}(R_{2}) ⊆ ⋯ in 𝔽_{2}^{n}, and thus r_{𝕏} = min{i ≥ 0 | ı_{i}(R_{i}) = ı_{i+1}(R_{i+1})}.

In the sequel, the image of X_{i} + I_{𝕏} ∈ R_{1} under ı_{1} will be denoted by v_{i} for i = 0, …, k. For v, w ∈ 𝔽_{q}^{n}, we let v · w be the component-wise product of v and w. We note that v^{p} = v, if q = p is a prime number. We also note that for all λ ≥ 1, the 𝔽_{q}-vector space ı_{λ}(R_{λ}) is generated by the products v_{i_{1}} ⋯ v_{i_{μ}} such that 0 ≤ i_{1} < ⋯ < i_{μ} ≤ k and 1 ≤ μ ≤ λ. In particular, in case q = 2, the equations v^{2} = v imply claim c) of the above proposition.

Proof of Proposition 1.2: The second claim s(2^{k+1} − 1, k, 2) = k + 1 is a special case of 1.4.e. The case l = k + 1 follows from 1.4.d. We start by reducing the proof of the proposition to the proof of the inequality

(∗)  s(n, k, 2) ≤ l − 1  for 2 ≤ l ≤ k + 1 and n < k + 2^{l} − l.

We argue by induction on k. Since the case k = 1 holds trivially, we may assume k ≥ 1 and 2 ≤ l ≤ k + 2 as well as (k + 1) + 2^{l−1} − (l − 1) ≤ n < (k + 1) + 2^{l} − l. From (∗) we get s(n, k + 1, 2) ≤ l − 1, so that we still need to show s(n, k + 1, 2) ≥ l − 1. If l = k + 2, we have 2^{k+1} ≤ n < 2^{k+2} − 1, and therefore s(n, k + 1, 2) = k + 1 = l − 1 by 1.4.d. If 2 ≤ l ≤ k + 1, we have k + 2^{l−1} − (l − 1) ≤ n − 1 < k + 2^{l} − l, and the induction hypothesis yields s(n − 1, k, 2) = l − 1. Now 2.2.b shows s(n, k + 1, 2) ≥ s(n − 1, k, 2) = l − 1, as claimed.

Thus we only need to prove (∗). Let 𝕏 ⊆ ℙ^{k}(𝔽_{2}) be a projective [n, k + 1]_{2}-system, let 2 ≤ l ≤ k + 1, and let n < k + 2^{l} − l. We want to show r_{𝕏} ≤ l − 1. By 2.4.b and 2.4.c, it suffices to show v_{i_{1}} ⋯ v_{i_{l}} ∈ ı_{l−1}(R_{l−1}) for all i_{1}, …, i_{l} ∈ {0, …, k}. Since v_{i}^{2} = v_{i}, we can assume 0 ≤ i_{1} < ⋯ < i_{l} ≤ k here. W.l.o.g. it suffices to show v_{0} ⋯ v_{l−1} ∈ ı_{l−1}(R_{l−1}).

Consider the set S = {v_{l}, …, v_{k}} ∪ {v_{i_{1}} ⋯ v_{i_{λ}} | 0 ≤ i_{1} < ⋯ < i_{λ} ≤ l − 1, 1 ≤ λ ≤ l} ⊆ ı_{l}(R_{l}). Since we have dim_{𝔽_{2}}(ı_{l}(R_{l})) = H_{𝕏}(l) ≤ n < k + 2^{l} − l = #S, the elements of S are 𝔽_{2}-linearly dependent. Choose the minimal number λ ≥ 1 such that there exists a relation of the form

v_{i_{1}} ⋯ v_{i_{λ}} = ∑_{j=l}^{k}a_{j}v_{j} + ∑_{0≤j_{1}<···<j_{μ}≤l−1, 1≤μ≤λ}b_{j_{1}...j_{μ}}v_{j_{1}} ⋯ v_{j_{μ}}

with 0 ≤ i_{1} < ⋯ < i_{λ} ≤ l − 1, and a_{j}, b_{j_{1}...j_{μ}} ∈ 𝔽_{2} such that b_{i_{1}...i_{λ}} = 0. Notice that we actually have λ ≥ 2, since {v_{0}, …, v_{k}} are 𝔽_{2}-linearly independent. If we multiply this relation with ∏_{j∈{0,...,l−1}\{i_{1},...,i_{λ}}} v_{j} and use the relations v_{i}^{2} = v_{i}, we see that v_{0} ⋯ v_{l−1} is in ⟨v_{i_{1}} ⋯ v_{i_{μ}} | 0 ≤ i_{1} < ⋯ < i_{μ} ≤ k, 1 ≤ μ ≤ l − 1⟩ = ı_{l−1}(R_{l−1}), as was to be shown. □

Also for the proof of 1.6 we need some preparations. First we recall some additional properties of Castelnuovo functions for sets of points in ℙ^{2} (cf. [3], [8]).

2.5. Proposition. Let 𝕏 ⊆ ℙ^{2}(𝔽_{q}) be a projective [n, 3]_{q}-system.

a) Let α_{𝕏} = min{ν ∈ ℕ | (I_{𝕏})_{ν} ≠ 0}. Then we have ΔH_{𝕏}(ν) = ν + 1 for 0 ≤ ν < α_{𝕏} and ΔH_{𝕏}(ν) ≥ ΔH_{𝕏}(ν + 1) for ν ≥ α_{𝕏} − 1 (cf. [3], 2.1).

b) If there are numbers d ≥ 1 and 0 ≤ r < r_{𝕏} such that ΔH_{𝕏}(r) = ΔH_{𝕏}(r + 1) = d, then there exists a subset 𝕐 ⊆ 𝕏 such that ΔH_{𝕐} = min{d, ΔH_{𝕏}}. In particular, this subset satisfies r_{𝕐} = r_{𝕏} (cf. [3], 2.2 and [8], 3.2).

We shall also need the following fact about the number of 𝔽_{q}-rational points on a (not necessarily irreducible) plane curve in ℙ_{\overline{𝔽}_{q}}^{2}, where \overline{𝔽}_{q} is the algebraic closure of 𝔽_{q}.

2.6. Proposition. Let C ⊆ ℙ_{\overline{𝔽}_{q}}^{2} be a plane curve of degree ν ≥ 1. Then the number of 𝔽_{q}-rational points C(𝔽_{q}) of C is at most νq + 1.

This follows easily from Bezout’s Theorem. For a more general statement for hypersurfaces in ℙ_{𝔽_{q}}^{k}, see [11], p. 1569.

Proof of Proposition 1.6: Claims a), d), and e) follow from the corresponding claims in 1.4. The last statement of e) was shown in [11]. For q + 2 ≤ n ≤ 2q + 1, claim b) follows from 1.4.b. For 2 ≤ ν ≤ q, we can choose 𝕏_{ν} ⊆ ℙ_{𝔽_{q}}^{2} to be the complete intersection of the curves C_{1} = Z(X_{1}(X_{1} − X_{0}) ⋯ (X_{1} − (ν − 1)X_{0})) and C_{2} = Z(X_{2}(X_{2} − X_{0}) ⋯ (X_{2} − (q − 1)X_{0})). Then 𝕏_{ν} consists of νq points of ℙ^{2}(𝔽_{q}), has Castelnuovo function ΔH_{𝕏_{ν}} : 1 2 ⋯ (ν − 1) ν ⋯ ν (ν − 1) ⋯ 2 1, and satisfies r_{𝕏_{ν}} = ν + q − 2. Thus we have s(n, 2, q) ≥ ν + q − 2 for 2 ≤ ν = ⌊\frac{n}{q}⌋ ≤ q.

In order to prove b) and c), it therefore suffices to show r_{𝕏} ≤ ν + q − 2 for every [n, 3]_{q}-system 𝕏 such that 2q ≤ n < q^{2} and ν = ⌊\frac{n}{q}⌋. Notice that we have 2 ≤ ν ≤ q − 1 here. We apply induction on n. For n = 2q, the claim follows from 1.4.b, as noted above. Now assume that n ≥ 2q + 1 and that there is a projective [n, 3]_{q}-system 𝕏 such that r_{𝕏} ≥ ν + q − 1 for ν = ⌊\frac{n}{q}⌋. For proper subsets 𝕐 ⊊ 𝕏, the induction hypothesis yields r_{𝕐} ≤ ν + q − 2. By 2.1.e, we get r_{𝕏} = ν + q − 1, and 2.6 together with n ≥ νq shows that 𝕏 is not contained in a curve of degree ν − 1.

Suppose 𝕏 is contained in a curve of degree ν. Then we have #X ≤ νq+1 by 2.6. Since no subset 𝕐 ⊊ 𝕏 satisfies r_{𝕐} = r_{𝕏}, Prop. 2.5 implies that ΔH_{𝕏} is of decreasing type, i.e. if ΔH_{𝕏}(i) > ΔH_{𝕏}(i + 1) for some i ≥ 1, then ΔH_{𝕏}(j) > ΔH_{𝕏}(j + 1) for all i ≤ j ≤ r_{𝕏}. Coupling this with α_{𝕏} = ν shows that ΔH_{𝕏} is of the form

ΔH_{𝕏} : 1 2 ⋯ (ν − 1) ν ν ⋯ ν (≥ ν − 1) ⋯ (≥ 2) (≥ 1).

Notice that there are r_{𝕏} + 1 values here, and there appears at least one value of ν. Hence we have #X = ∑_{i=0}^{r_{𝕏}} ΔH_{𝕏}(i) ≥ ν(q + 1) ≥ νq + 2, contradicting the above inequality.

Thus 𝕏 is not contained in a curve of degree ν, i.e. we have α_{𝕏} ≥ ν + 1. Again we can use 2.5 to conclude that ΔH_{𝕏} has to be of decreasing type and of the form

ΔH_{𝕏} : 1 2 ⋯ (ν − 1) ν ⋯ α_{𝕏} α_{𝕏} ⋯ α_{𝕏} (≥ α_{𝕏} − 1) ⋯ (≥ 2) (≥ 1).

Hence we get n = #𝕏 ≥ (ν + 1)q, contradicting ν = ⌊\frac{n}{q}⌋. Altogether, we find that every projective [n, 3]_{q}-system 𝕏 as above satisfies r_{𝕏} ≤ ν + q − 2, as was to be shown. □

3. Applications

Coding Theory. There is a close connection between projective [n, k + 1]_{q}- systems and linear [n, k + 1]_{q}-codes, i.e. codes of length n and dimension k +1 (cf. [12]). This connection allows another interpretation of the numbers s(n, k, q) and s(n, q) which we are now going to explain.

If 𝕏 = {P_{1}, …, P_{n}} ⊆ ℙ^{k}(𝔽_{q}) is a projective [n, k + 1]_{q}-system, and if we choose homogeneous coordinates P_{i} = (p_{i0}, …, p_{ik}) for i = 1, …, n, then the matrix (p_{ij}) is the generating matrix of a linear [n, k + 1]_{q}-code without repetitions, i.e. with pairwise linearly independent columns. In this way we obtain a 1-1 correspondence between 𝔽_{q}-isomorphism classes of projective [n, k + 1]_{q}-systems and equivalence classes of linear [n, k + 1]_{q}-codes without repetitions. Here two linear codes of length n are called equivalent, if they can be transformed into each other by a linear transformation in S_{n} ⋉ (𝔽_{q}^{∗})^{n} ⊆ GL_{n}(𝔽_{q}).

Let C be a code representing the equivalence class corresponding to a projective [n, k + 1]_{q}-system 𝕏 ⊆ ℙ^{k}(𝔽_{q}). For ν ≥ 1, the code C^{ν} ⊆ 𝔽_{q}^{n} generated by the component-wise products c_{1} ⋯ c_{ν} sucht that c_{1}, …, c_{ν} ∈ C is called the Reed-Muller code of order ν associated to C. It follows from [6] that C^{ν} is a linear [n, H_{𝕏}(ν)]_{q}-code. Summarizing this discussion, we obtain the following interpretations for r_{𝕏}, s(n, k, q) and s(n, q).

3.1. Proposition. Let 𝕏 ⊆ ℙ^{k}(𝔽_{q}) be a projective [n, k + 1]_{q}-system, and let C ⊆ 𝔽_{q}^{n} be a linear code associated to 𝕏. Furthermore, let r(C) denote the number of different (i.e. non-equivalent) Reed-Muller codes C^{ν} with ν ≥ 1.

a) We have r(C) = r_{𝕏}.

b) We have s(n, k, q) = max{r(C) |C linear [n, k + 1]_{q}-code}.
c) We have s(n, q) = max{r(C) | C ⊆ 𝔽_{q}^{n} linear code}.

Commutative Algebra. For a commutative, 1-dimensional, local Cohen-Macaulay ring R with maximal ideal 𝔪, the index of stability s(R) is defined as follows (cf. [7]). If 𝔞 ⊆ R is an 𝔪-primary ideal, then the least positive integer such that 𝔞^{n} is stable, i.e. such that 𝔞^{2n} = x 𝔞^{n} for some x ∈ 𝔞^{n}, is denoted by n(𝔞). Then we let

s(R) = sup{n(𝔞) | 𝔞 ⊆ R 𝔪-primary ideal}.

In this language, we can interpret s(n, q) as follows.

3.2. Proposition. For the commutative, 1-dimensional, local Cohen-Ma-caulay ring R_{q} = 𝔽_{q}[[X_{1}, …, X_{n}]]/(X_{i}X_{j})_{1≤i<j≤n} we have s(R_{q}) = s(n, q). In particular, this implies s(R_{2}) = ⌊log_{2}(n + 1)⌋ by 1.3 and s(R_{q}) ≤ \frac{1}{2}(n + 1) for n ≥ 2q − 1 by 1.5.

The straightforward proof of this result is left to the reader. We note that [7], Example 3.c, amounts to s(R_{2}) ≤ \frac{1}{2}(n + 1).

Boolean Algebra. For a finite set A, we consider the Boolean algebra 𝔓(A) consisting of all of its subsets. The algebra structure of 𝔓(A) is described by taking intersections B·C = B∩C and symmetric differences B+C = (B∩(A\ C))∪(C ∩(A\B)). Let B_{1}, …, B_{k} be subsets of A, and ⟨B_{1}, …, B_{k}⟩ ⊆ 𝔓(A) the subalgebra generated by them. The minimal number i(B_{1}, …, B_{k}) such that every element of ⟨B_{1}, …, B_{k}⟩ is a sum of products of the form B_{i_{1}} ⋯ B_{i_{ν}} with ν ≤ i(B_{1}, …, B_{k}) is called the intersection number of B_{1}, …, B_{k}. We call B_{1}, …, B_{k} independent, if no B_{i} is a symmetric difference of some of the elements B_{j} with j ≠ i.

Moreover, the number i(A) = max{i(B_{1}, …, B_{k}) | k ≥ 1, B_{1}, …, B_{k} ∈ 𝔓(A)} is called the maximal intersection number of 𝔓(A) (cf. [1]). Again we leave it as an exercise for the interested reader to check the following interpretation of our invariants s(n, k, 2) and s(n, 2).

3.3. Proposition. Let A be a finite set consisting of n elements.

a) We have s(n, k, 2) = max{i(B_{1}, ⋯, B_{k+1}) | B_{1}, …, B_{k+1} ∈ 𝔓(A) independent }.

b) We have i(A) = s(n, 2).

References

[1] R. Beinhauer, Die maximale Schnittzahl bei der Erzeugung endlicher Mengenalgebren, unpublished manuscript 1975

[2] A. Capani, G. Niesi, and L. Robbiano, CoCoA 3, a system for doing computations in commutative algebra, Universitá di Genova 1995, available via anonymous FTP from lancelot.dima.unige.it

[3] E. Davis, 0-dimensional subschemes of ℙ^{2}: new applications of Castelnuovo’s function, Ann. Univ. Ferrara Sez. VII 32 (1986), 93–107

[4] A.V. Geramita, M. Kreuzer, and L. Robbiano, Cayley-Bacharach schemes and their canonical modules, Trans. Amer. Math. Soc. 339 (1993), 163–189 [5] A.V. Geramita, P. Maroscia and L.G. Roberts, The Hilbert function of

a reduced k-algebra, J. London Math. Soc. (2) 28 (1983), 443–454 [6] J.P. Hansen, Points in uniform position and maximum distance sepa-

rable codes, in: L. Chiantini and F. Orecchia (eds.), Zero-dimensional schemes, Proc. Conf. Ravello 1992, de Gruyter, Berlin 1994

[7] J. Herzog and R. Waldi, A note on the Hilbert function of a onedimensional Cohen-Macaulay ring, Manus. Math. 16 (1975), 251–260

[8] B. Kreuzer and M. Kreuzer, Extremal zerodimensional subschemes of ℙ^{2}, J. Pure Appl. Algebra (to appear)

[9] M. Kreuzer and L. Robbiano, On maximal Cayley-Bacharach schemes, Comm. in Algebra 23 (1995), 3357–3378

[10] J.H. van Lint, Introduction to coding theory, Grad. Texts in Math. 86, Springer, Berlin 1982

[11] A.B. Sørensen, Projective Reed-Muller codes, IEEE Trans. on Information Theory 37 (1991), 1567–1576

[12] M. Tsafasman and S.G. Vladut, Algebraic-geometric codes, Kluwer Acad. Publ., Dordrecht 1991