Algorithms for Checking Uniformity Conditions and Applications in Coding Theory

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

1.1. Definition. The scheme 𝕏 is called a Cayley-Bacha-rach scheme (CB-scheme) ⇔ ⇔ every hypersurface of degree σ_{𝕏} containing a subscheme 𝕐 ⊂ 𝕏 of degree deg(𝕐) = deg(𝕏) − 1 contains 𝕏 ⇔ ⇔ for every subscheme 𝕐 ⊂ 𝕏 of degree deg(𝕐) = deg(𝕏)−1 we have H_{𝕐}(σ_{𝕏}) = H_{𝕏}(σ_{𝕏}).

1.2. Proposition. (CB-Schemes Under Liaison, cf. [KR],4.1)

Let 𝕍 ⊂ ℙ_{K}^{n} be an arithmetically Gorenstein 0-dimen-sional 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.

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 inorder to get a contradiction. Let G ∈ (I_{𝕐/𝕍})_{α_{𝕐/𝕍}}. Then G · F ∈ I_{𝕍} and G · I_{𝕏} ⊆ I_{𝕍} imply G · I_{𝕏′} ⊆ I_{𝕍}, and in particular G ∈ (I_{𝕐′/𝕍})_{α_{𝕐/𝕍}}. □

2. Checking Higher Uniformity Conditions

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).

2.2. Remarks. a) If 𝕏 is (i, j)-uniform, then X is also (k, j)- uniform for 1 ≤ k ≤ i.

b) If 𝕏 is (i, j)-uniform, then i ≤ deg(𝕏) − H_{𝕏}(j).

2.3. Examples. a) 𝕏 is a CB-scheme ⇔ 𝕏 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 ⇔ 𝕏 is (deg(𝕏) − n − 1, 1)-uniform.

c) 𝕏 is in uniform position (a la J. Harris), i.e. any subscheme 𝕐 ⊆ 𝕏 satisfies H_{𝕐} = min{deg(𝕐), H_{𝕏}} ⇔ 𝕏 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 = σ_{𝕏}.

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

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 ⇔ 𝕏 is (2, i)-uniform.

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

Question 1: How can one check (i, j)-uniformity effectively if I_{𝕏} ⊂ P is given? Question 2: Can one use the Liaison technique for cases other than checking (1, σ_{𝕏})-uniformity?

2.3. Proposition. (cf. [GKR], 2.13) 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.

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 analogy with [BK], it can be computed as follows.

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

b) 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 Rmodule structure of ω_{R} = (⊕_{i=1}^{s}K[x_{0}] · p_{i})(−1).

c) 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}. d) Minimalize the presentation ⨁_{i=1}^{r} P (deg(t_{μ_{i}})−1)−↠ ω_{R}

using standard techniques.

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

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. Proof: This follows in a similar fashion as [K2], 3.2. □

In order to check whether the map μ_{j} is 1-generic, we may use one of the following two methods. 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.

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.

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}. 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)-unifor-mity of 𝕏 and the minimal distance of the codes constructed via Proposition 4.3? How should one choose the maps π_{i}?