Algorithms for Checking Uniformity Conditions and Applications in Coding Theory

by Martin Kreuzer (Regensburg)

Abstract. In the first part of this paper, we generalize the characterization of Cayley-Bacharach schemes using Liaison given in [GKR], 4.6, to the non-reduced case (cf. [KR], 4.1). Then we show how one can apply this result to develop an algorithm for checking the Cayley-Bacharach property in the non-reduced case (cf. [K1], 16.9).

We shall also discuss algorithms for checking higher uniformity properties of reduced 0-dimensional schemes, especially for checking the (i, j)-uniformities introduced in [K1], 7.12 and [K2], 5.6. Using Hansen’s construction (cf. [H]), we can interpret these algorithms as algorithms for computing the minimal distance of a linear code.

Possible generalizations include a version of Hansen’s construction for the nonreduced case and algorithms for checking (i, j)-uniformity in the non-reduced case.

Notations. Let K be a field, 𝕏 ⊂ ℙ_{K}^{n} a 0-dimensional subscheme, P = K[x_{0}, …, x_{n}] the polynomial ring, I_{𝕏} ⊂ P the homogeneous vanishing ideal of 𝕏, and R = P/I_{𝕏} the homogeneous coordinate ring of 𝕏.

Furthermore, let H_{𝕏} : ℤ → ℕ (i ↦ dim_{K}(R_{i})) be the Hilbert function of 𝕏 and σ_{𝕏} = max{i ∈ ℤ | H_{𝕏}(i) < deg(𝕏)}.

1. Checking the Cayley-Bacharach Property

The idea behind the algorithms presented in this paper is to use results from algebraic geometry in order to be able to effectively check certain geometric properties of 0-dimensional schemes. The first example is an algorithm for checking the Cayley-Bacharach property which is based on the characterization of this property using liaison techniques.

1.1. Definition. The scheme 𝕏 is called a Cayley-Bacharach scheme (CB-scheme) if and only if every hypersurface of degree σ_{𝕏} containing a subscheme 𝕐 ⊂ 𝕏 of degree deg(𝕐) = deg(𝕏) − 1 contains 𝕏. Equivalently, 𝕏 is a Cayley-Bacharach scheme if and only if, for every subscheme 𝕐 ⊂ 𝕏 of degree deg(𝕐) = deg(𝕏) − 1, we have H_{𝕐}(σ_{𝕏}) = H_{𝕏}(σ_{𝕏}).

The following characterization of Cayley-Bacharach schemes was shown in [KR], 4.1, and generalizes the corresponding result in the reduced case (cf. [GKR], 4.6).

1.2. Proposition. (CB-Schemes Under Liaison)

Let 𝕍 ⊂ ℙ_{K}^{n} be an arithmetically Gorenstein 0-dimensional scheme containing 𝕏, and let 𝕐 ⊂ 𝕍 be the residual scheme of 𝕏 in 𝕍. The following conditions are equivalent:

a) 𝕏 is a Cayley-Bacharach scheme.

b) For every subscheme 𝕐′ ⊆ V containing 𝕐 of degree deg(𝕐′) = deg(𝕐) + 1 we have

(I_{𝕐′/𝕍})_{α_{𝕐/𝕍}} ⊊ (I_{𝕐/𝕍})_{α_{𝕐/𝕍}}

Here I_{𝕐/𝕍} is the ideal of 𝕐 in the coordinate ring of 𝕍 and α_{𝕐/𝕍} is its initial degree.

The complete proof of the following corollary is contained in [K1], 16.9. Here we recall only the proof of one implication which is indicative of the method and shows how Proposition 1.2 comes into play.

1.3. Corollary. The following conditions are equivalent.

a) 𝕏 is a Cayley-Bacharach scheme.

b) I_{𝕍} : (I_{𝕐})_{α_{𝕐/𝕍}} = I_{𝕏}

c) dim_{K}(P/(I_{𝕍} : (I_{𝕍} : I_{𝕏})_{α_{𝕐/𝕍}}))_{σ_{𝕏}} = H_{𝕏}(σ_{𝕏})

Condition c) can be checked by computing two truncated Gröbner bases.

Proof: “a)⇒b)” Let F ∈ P be a homogeneous polynomial such that F · (I_{𝕐})_{α_{𝕐/𝕍}} ⊆ I_{𝕍}, but F ∉ I_{𝕏}. Let 𝕏′ ⊆ 𝕏 contain Z(I_{𝕏}, F) and have degree deg(𝕏′) = deg(𝕏) − 1. Let 𝕐′ ⊆ 𝕍 be the residual scheme of 𝕏′ in 𝕍. It suffices to prove equality in 1.2.b in order to get a contradiction. Let G ∈ (I_{𝕐/𝕍})_{α_{𝕐/𝕍}}. Then G · F ∈ I_{𝕍} and G · I_{𝕏} ⊆ I_{𝕍} imply G · I_{𝕏′} ⊆ I_{𝕍}, and in particular G ∈ (I_{𝕐′/𝕍})_{α_{𝕐/𝕍}}. □

1.4. Algorithm. Suppose a 0-dimensional subscheme 𝕏 ⊂ ℙ_{K}^{n} is given via its vanishing ideal I_{𝕏}. Consider the following instructions.

1) Choose a homogeneous regular sequence f_{1}, …, f_{n} ∈ I_{𝕏}. (If K is infinite, we can for instance take generic polynomials in (I_{𝕏})_{σ_{𝕏}+2}.) Let I_{𝕍} = (f_{1}, …, f_{n}).

2) Compute I_{𝕍} : I_{𝕏} degree by degree, until we reach the first degree α such that V = (I_{𝕍} : I_{𝕏})_{α} ≠ 0.

3) Compute W = (I_{𝕍} : V)_{σ_{𝕏}} using a truncated Gröbner basis calculation.

4) Check whether dim_{K}(W) = H_{𝕏}(σ_{𝕏}) and return the corresponding Boolean value. This is an algorithm which checks effectively whether 𝕏 is a Cayley-Bacharach

scheme.

Notice that, if 𝕏 is not locally Gorenstein, there is no direct way to check whether 𝕏 is a Cayley-Bacharach scheme, because it contains infinitely many subschemes of degree deg(𝕏) − 1.

2. Checking Higher Uniformity Conditions

The Cayley-Bacharach property is merely the weakest of a whole series of uniformity conditions which a 0-dimensional subscheme X ⊂ ℙ_{K}^{n} can satisfy. The following very general uniformity concepts were introduced in [K1], 7.12 and [K2], 5.6.

2.1. Definition. Let 1 ≤ i < deg(𝕏) and 1 ≤ j ≤ σ_{𝕏}. The scheme 𝕏 is called (i , j)-uniform iff every subscheme 𝕐 ⊂ 𝕏 of degree deg(𝕐) = deg(𝕏) − i satisfies H_{𝕐}(j) = H_{𝕏}(j).

Using the following remark, one can easily picture the uniformity of a 0-dimensional scheme as a bounded region in the (i, j)-plane.

2.2. Remarks. a) If 𝕏 is (i, j)-uniform, then 𝕏 is also (k, j)-uniform for 1 ≤ k ≤ i. b) If 𝕏 is (i, j)-uniform, then i ≤ deg(𝕏) − H_{𝕏}(j).

c) If 𝕏 is (i, j)-uniform, then 𝕏 is also (i, k)-uniform for all 1 ≤ k ≤ j.

Although at first glance the conditions introduced in Definition 2.1 may appear esoteric, the following example shows that they generalize many well-known uniformity conditions.

2.3. Examples. a) 𝕏 is a CB-scheme if and only if 𝕏 is (1, σ_{𝕏})-uniform.

b) Let H_{𝕏}(1) = n+1. Then 𝕏 is in linearly general position, i.e. every subscheme 𝕐 ⊆ 𝕏 of degree n+1 satisfies H_{𝕐}(1) = n+1 if and only if 𝕏 is (deg(𝕏)−n−1, 1)-uniform.

c) The scheme 𝕏 is in uniform position (a la J. Harris), i.e. any subscheme 𝕐 ⊆ 𝕏 satisfies H_{𝕐} = min{deg(𝕐), H_{𝕏}} if and only if 𝕏 is (deg(𝕏) − H_{𝕏}(j), j)-uniform for 1 ≤ j ≤ σ_{𝕏}.

d) The Eisenbud-Green-Harris conjecture says that if 𝕏 is (reduced and) the complete intersection of n quadrics, then 𝕏 is (2^{n−j} − 1, j)-uniform for 1 ≤ j ≤ n = σ_{𝕏} (see [EGH], Conjecture III_{k,r}).

e) Let 𝕏 be reduced and ω_{R} the canonical module of R. One can use (ω_{R})_{−1} to define the Gale transform of 𝕏 (see [K2], 5.3). It consists of deg(𝕏) distinct points if and only if 𝕏 is (2, 1)-uniform (see [K2], 5.2).

f) Let 𝕏 be reduced and 1 ≤ i ≤ σ_{𝕏}. One can use (ω_{R})_{−i} to define the i^{th} canonical transform of 𝕏. It consists of deg(𝕏) distinct points if and only if 𝕏 is (2, i)-uniform (see [K2], 5.8 and 5.9).

g) The concept of (i, j)-uniformity is also connected to Hansen’s construction (see later).

The main question addressed in this paper is therefore:

Question 1: How can one check (i, j)-uniformity effectively if I_{𝕏} ⊂ P is given?

Looking back at Section 1, we naturally ask ourselves:

Question 2: Can one use the Liaison technique for cases other than checking (1, σ_{𝕏})- uniformity?

A small step towards a positive answer to Question 2 was done during the Naples workshop, where I used liaison to prove the following result.

2.3. Proposition. Let Δ_{𝕏} = H_{𝕏}(σ_{𝕏} + 1) − H_{𝕏}(σ_{𝕏}), and suppose that 𝕏 is (Δ_{𝕏}, σ_{𝕏})- uniform. Moreover, let 𝕍 be a 0-dimensional arithmetically Gorenstein scheme containing 𝕏, let 𝕐 be the residual scheme of 𝕏 in 𝕍, and let α = α_{𝕐/𝕍} be the initial degree of the ideal of 𝕐 in the coordinate ring of 𝕍. Then the following conditions are equivalent.

a) The scheme 𝕏 is (Δ_{𝕏} + 1, σ_{𝕏} − 1)-uniform.

b) We have (I_{𝕍} : (I_{𝕐})_{α+1})_{σ_{𝕏}−1} = (I_{𝕏})_{σ_{𝕏}−1}.

Apart from this result, only few cases are known where one can determine whether 𝕏 is (i, j)-uniform. If 𝕏 is reduced and j = σ_{𝕏} the maximum possible number, then we can use a result shown in [GKR], 2.13.

2.4. Proposition. Let 𝕏 ⊂ ℙ_{K}^{n} \Z(x_{0}) be a set of s reduced points, and let f_{1}, …, f_{s} ∈ R_{σ_{𝕏}+1} be the separators of 𝕏. Then the following conditions are equivalent for 1 ≤ i ≤ deg(𝕏) − H_{𝕏}(σ_{𝕏}):

a) 𝕏 is (i, σ_{𝕏})-uniform.

b) Any i elements of {f̄_{1}, …, f̄_{s}} ⊂ (R/(x_{0}))_{σ_{𝕏}+1} are K-linearly independent. Condition b) can be checked effectively by computing \binom{s}{i} determinants of matrices

of size i × i over K.

Moreover, it appears that a similar procedure can be devised if j = σ_{𝕏} and 𝕏 is not reduced.

3. The Canonical Module

As before, let 𝕏 ⊂ ℙ_{K}^{n} be a 0-dimensional subscheme. By extending K if necessary, we may assume that there exists a hyperplane which misses all points of Supp (𝕏), and w.l.o.g. this holds for Z(x_{0}). Then the canonical module of R is given by

ω_{R} ≅ \underline{Hom}_{K[x_{0}]}(R, K[x_{0}])(−1)

In [BK], we showed how one can compute a presentation of ω_{R} for reduced schemes 𝕏. It is not difficult to check that this algorithm can be generalized to the non-reduced case as follows.

3.1. Algorithm. Let 𝕏 be a 0-dimensional subscheme of ℙ_{K}^{n}, and let 𝕋^{n} be the monoid of terms (monomials) in P. Consider the following instructions.

1) Let s = deg(𝕏), and let t_{1}, …, t_{s} ∈ 𝕋^{n} be terms in K[x_{1}, …, x_{n}] whose residue classes form a K-basis of R. Compute those terms by computing LT_{σ}(I_{𝕏}|_{x_{0}=0}) for some term ordering σ.

2) Let p_{i} : R ⟶ K[x_{0}] (t_{j} ↦ δ_{ij}) be the dual K[x_{0}]-basis of ω_{R}. Find c_{ijk} ∈ K[x_{0}] such that t_{i}t_{k} = ∑_{j=1}^{s} c_{ijk}t_{j} holds in R. Then t_{i}p_{j} = ∑_{k=1}^{s} c_{ijk}p_{k} determines the R-module structure of ω_{R} = (⊕_{i=1}^{s}K[x_{0}] · p_{i})(−1).

3) Choose the set {t_{μ_{1}}, …, t_{μ_{r}}} of socle monomials in {t_{1}, …, t_{s}}, i.e. the set

{t ∈ 𝕋^{n} \ LT_{σ}{I_{𝕏}|_{x_{0}=0}} | x_{i}t ∈ LT_{σ}{I_{𝕏}|_{x_{0}=0}} for i = 1, …, n}

Then {p_{μ_{1}}, …, p_{μ_{r}}} is a minimal Gröbner basis of ω_{R}.

4) Minimalize the presentation ⨁_{i=1}^{r} P (deg(t_{μ_{i}})−1)−↠ ω_{R} using standard techniques.

This is an algorithm which yields a minimal presentation of the P -module ω_{R}. We may explicitly compute the multiplication maps R_{i} ⊗ (ω_{R})_{j} ⟶ (ω_{R})_{i+j} for i ≥ 0 and j ≥ −σ_{𝕏}.

The canonical module ω_{R} can be used to check (i, j)-uniformity of 𝕏 if i is the maximum possible number i = deg(𝕏) − H_{𝕏}(j). The algorithm for doing this is based on our next proposition which can be shown along the lines of the proof of [K2], 3.2.

3.2. Proposition. For 1 ≤ j ≤ σ_{𝕏}, the following conditions are equivalent. a) 𝕏 is (deg(𝕏) − H_{𝕏}(j), j)-uniform.

b) The multiplication map μ_{j} : R_{j} ⊗ (ω_{R})_{−j} ⟶ (ω_{R})_{0} is 1-generic, i.e. it satisfies μ_{j}(r ⊗ w) = 0 ⇒ r = 0 or w = 0.

In order to check whether the map μ_{j} is 1-generic, we may use one of the following two methods (see [BK], 8.3 and 8.4).

3.3. Proposition. Let μ : U × V ⟶ W be a K-linear map of finite dimensional K-vector spaces, let {u_{1}, …, u_{ℓ}} be a basis of U, let {v_{1}, …, v_{m}} be a basis of V, and {w_{1}, …, w_{n}} a basis of W. Write μ(u_{λ} ⊗ v_{μ}) = ∑_{ν=1}^{n} c_{λμν}w_{ν} with elements c_{λμν} ∈ K.

a) Consider the polynomials q_{ν} = ∑_{λ,μ} c_{λμν}Y_{λ}Z_{μ} in K[Y_{1}, …, Y_{ℓ}, Z_{1}, …, Z_{m}]. Then μ is 1-generic if and only if (Y_{λ}Z_{μ})_{λ,μ} ⊆ Rad(q_{1}, …, q_{n}). This can be decided effectively using the radical membership test.

b) (D. Eisenbud) For ν = 1, …, n let C_{ν} = (c_{λμν})_{λ,μ}, and let M = ⟨C_{1}, …, C_{n}⟩ ⊆ Hom_{K}(K^{m}, K^{ℓ}). By solving a linear system of equations, we can determine a K-basis {D_{1}, …, D_{ℓm−n}} of

M^{⊥} = {D ∈ Hom_{K}(K^{m}, K^{ℓ}) | tr(DC_{1}) = ⋯ = tr(DC_{n}) = 0}

Let E = D_{1}Y_{1} + ⋯ + D_{ℓm−n}Y_{ℓm−n} be the corresponding matrix of linear forms. Then μ is 1-generic iff Rad(I_{2}(E)) = (Y_{1}, …, Y_{ℓm−n}). This can be decided again using the radical membership test.

Question 3: Can one use the canonical module to check (i, j)-uniformity also for 1 ≤ i < deg(𝕏) − H_{𝕏}(j)?

4. Hansen’s Construction

A linear code C over K = 𝔽_{q}, where q = p^{e} with a prime p and e > 0, is an 𝔽_{q}-subvector space C ⊆ 𝔽_{q}^{s}. The number s is called the length of the code, d = d(C) = dim_{𝔽_{q}}(C) is called the dimension of C, and the minimal number m = m(C) of nonzero entries in a nonzero vector of C is called the minimal distance of C.

The basic invariants s, d, and m of a linear code are related by the following well-known result.

4.1. Proposition. (Singleton Bound) For every linear code C ⊆ 𝔽_{q}^{s} we have m(C) ≤ s − d(C) + 1. A code achieving this bound is called an MDS-code.

In order to find “good” codes, i.e. codes coming close to the Singleton bound, J.P. Hansen introduced the following construction (see [H], Prop. 6 and Thm. 8 and [K2], Section 5).

4.2. Proposition. (Hansen’s Construction) Let 𝕏 = {P_{1}, …, P_{s}} ⊆ ℙ_{𝔽_{q}}^{n} \ Z(x_{0}) be a finite set of points, and let 1 ≤ j ≤ σ_{𝕏}.

a) The image of the injective 𝔽_{q}-linear map

\begin{matrix}Φ_{j} : R_{j} & ⟶ & 𝔽_{q}^{s} \\ f & ⟼ & (f(P_{1}), …, f(P_{s})) \end{matrix}

is a linear code of length s and dimension H_{𝕏}(j). This code is called the j^{th} Reed-Muller code associated to 𝕏 and denoted by C^{j}(𝕏) = im(Φ_{j}).

b) For every i ≥ 1, we have m(C) ≥ s − i + 1 if and only if 𝕏 is (s − i, j)-uniform.

Every linear code can be obtained as Φ_{1}(𝕏) for some finite point set 𝕏 ⊆ ℙ_{𝔽_{q}}^{n}. Thus, to compute the minimal distance of a linear code is equivalent to determining the uniformity of the corresponding 0-dimensional scheme 𝕏.

In this way, our results in the previous three sections can be interpreted as algorithms for computing the minimal distances of linear codes in some special cases. They should be compared with similar algorithms presented in [CCS], Ch. 10, Section 3.

If 𝕏 is not necessarily reduced, we can generalize Hansen’s construction as follows.

4.3. Proposition. Let X ⊆ ℙ_{𝔽_{q}}^{n} be a 0-dimensional subscheme such that 𝕏∩Z(x_{0}) = ∅. Let J_{𝕏} = I_{𝕏}^{dehom.} ⊂ Q = K[x_{1}, …, x_{n}] be the affine vanishing ideal of 𝕏. Suppose we know the primary decomposition J_{𝕏} = 𝔮_{1} ∩ ⋯ ∩ 𝔮_{s} of J_{𝕏}. Choose 𝔽_{q}-subvector spaces V_{i} ⊂ Q such that π_{i} : Q ⟶ V_{i} ≅ Q/𝔮_{i} is effectively computable. (For instance, let V_{i} be generated by the terms outside some leading term ideal of 𝔮_{i}.)

Then, for each i ∈ {1, …, σ_{𝕏}}, the image of the 𝔽_{q}-linear map

\begin{matrix}Φ_{j} : R_{j} & ⟶ & V_{1} × ⋯ × V_{s} ≅ 𝔽_{q}^{deg(𝕏)} \\ f & ⟼ & (π_{1}(f^{a}), …, π_{s}(f^{a})) \end{matrix}

is a linear code C^{j}(𝕏) of length deg(𝕏) and dimension H_{𝕏}(j).

Question 4: Does the construction of Proposition 4.3 yield interesting new codes?

Question 5: What is the relation between the (i, j)-uniformity of 𝕏 and the minimal distance of the codes constructed via Proposition 4.3? In particular, how should one choose the maps π_{i} in order to get such a relation?

Acknowledgements. First of all, I would like to thank F. Orecchia and the organizing committee for inviting me to present this work during the workshop and for the stimulating atmosphere in Naples. Furthermore, I am deeply indebted to the CoCoA project headed by L. Robbiano and the CNR for their support.

References

[BK] S. Beck and M. Kreuzer, How to compute the canonical module of a set of points, in: L. Gonzales-Vega and T. Recio (eds.), Algorithms in Algebraic Geometry and Applications, Proc. Conf. MEGA ’94, Santander 1994, Progress in Math. 143, Birkhäuser Verlag, Basel 1996, 51 – 78

[CCS] A. Cohen, H. Cuypers, and H. Sterk, Some tapas of computer algebra, Algorithms and Computation in Mathematics 4, Springer, Heidelberg 1999

[EGH] D. Eisenbud, M. Green, and J. Harris, Higher Castelnuovo theory, in: Journees de geometrie algebrique d’Orsay, Proc. Conf. Orsay / France 1992, Asterisque 218 (1993), 187 – 202

[GKR] A.V. Geramita, M. Kreuzer, and L. Robbiano, Cayley-Bacharach schemes and their canonical modules, Trans. Amer. Math. Soc. 339 (1993), 163 – 189

[H] J.P. Hansen, Points in uniform position and maximum distance separable codes, in: F. Orecchia and L. Chiantini (eds.), Zero-Dimensional Schemes, Proc. Conf. Ravello 1992, de Gruyter, Berlin 1994, 205 – 211

[K1] M. Kreuzer, Beiträge zur Theorie der nulldimensionalen Unterschemata projektiver Räume, Regensburger Math. Schr. 26, Universität Regensburg 1998, xvi + 128 p.

[K2] M. Kreuzer, On the canonical ideal of a set of points, Boll. Un. Mat. Ital. (8) 1-B (2000), 221 – 261

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

Address of the author.

PD Dr. Martin Kreuzer Fakultät für Mathematik Universität Regensburg D-93040 Regensburg Germany