Algebraic notes on testing sets for lower and upper grids

Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Factorization of matrices (15A23) Vector and tensor algebra, theory of invariants (15A72) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Interpolation in approximation theory (41A05)

Review text

In a broad sense, Lagrange interpolation consists of the following. Let \(k\) be a field, \(\mathcal{A}\) be an arbitrary set and \(\mathcal{P}\) be a finite-dimensional vector subspace of the functional space \(k^{\mathcal{A}}\). Then, given a subset \(\mathcal{N}\) of elements of \(\mathcal{A}\), called nodes, and some data in each node (a mapping \(y: \mathcal{N} \rightarrow k\)), we may ask for a function \(f \in \mathcal{P}\) that agrees with \(y \in \mathcal{N}\). We say that the pair \((\mathcal{P}, \mathcal{N})\) is \textit{poised for interpolation} whenever any data \(y \in k^{\mathcal{N}}\) can be interpolated by a unique function of \(\mathcal{P}\) (see, for example, [\textit{M. Gasca} and \textit{T. Sauer}, Adv. Comput. Math. 12, No. 4, 377--410 (2000; Zbl 0943.41001)]). \N\NIn the paper under review, the following case is considered. The set \(\mathcal{A}\) is the \(n\)-dimensional affine space \(k^n\), the space \(\mathcal{P}\) consists of polynomial functions generated by polynomials in \(k[ x_1, \cdots, x_n]\) and the nodes for interpolation are selected from a cartesian product \(\mathcal{X} = \mathcal{X}_1 \times \cdots \times \mathcal{X}_n\), where \(\mathcal{X}_i = \{ x_{i0}, x_{i1}, \ldots, x_{ij}, \ldots \}\) are sets of independent variables \(x_{ij}\), which can later be replaced by elements of \(k\).\N\NMore precisely, let \(\mathcal{C}\) be a \textit{grid} (i.e., a finite subset of \(\mathbb{N}_0^n\)) and define \(\mathcal{X_C} := \{ (x_{1 \tau_1} , \ldots , x_{n \tau_n}) : (\tau_1, \cdots , \tau_n) \in \mathcal{C} \}\). Let \(\mathcal{B}\) be a finite set of monomials \(x^{\alpha} = x^{\alpha_1}_1 x^{\alpha_2}_2 \cdots x^{\alpha_n}_n\), where \(\alpha = (\alpha_1, \cdots, \alpha_n) \in \mathbb{N}_0^n\). Such a set can be identified with a grid via the correspondence \(x^\alpha \mapsto \alpha\). Evaluating a monomial \(x^{\alpha} \in \mathcal{B}\) at a node \((x_{1 \tau_1} , \ldots , x_{n \tau_n}) \in \mathcal{X_\mathcal{C}}\) produces an element \(x^{\alpha_1}_{1\tau_1} \cdots x^{\alpha_n}_{n \tau_n}\) of the field of fractions \(\mathbb{K} = k (\{ x_{ij} \})\) and we can define the evaluation map\N\[\N\mathrm{Ev}_{\mathcal{B,C}} : \mathfrak{P}_\mathcal{B} \longrightarrow \mathbb{K}^{\mathcal{X_C}},\N\]\Nwhere \(\mathfrak{P}_\mathcal{B}\) is the \(\mathbb{K}\)-subspace of \(\mathbb{K}[x_1, \ldots, x_n]\) generated by \(\mathcal{B}\). We say that \(\mathcal{B}\) is a \(\sigma\)-lower (resp., \(\sigma\)-upper) grid if it is a union of intervals of \(\mathbb{N}^n_0\) with common origin \(\sigma\) (resp., endpoint \(\sigma\)). When \(\mathcal{B} = \mathcal{C}\) and \(\mathcal{B}\) is a \(\sigma\)-lower (resp., \(\sigma\)-upper) grid, the author provides (Theorem 9) explicit formulas for \(\det \mathbb{V}[\mathcal{B}]\), the determinant of \(\mathrm{Ev}_{\mathcal{B,B}}\), and proves (Corollary 10) that if \(\mathcal{B} \subseteq \mathcal{B}'\) are \(\sigma\)-lower grids, then\N\[\N\det \mathbb{V}[\mathcal{B}] \mid \det \mathbb{V}[\mathcal{B}'].\N\]\NAdditionally, the author proves (Theorem 5) that the pairs \((\mathfrak{P}_\mathcal{B}, \mathcal{X_B})\) are poised for interpolation for any grid \(\mathcal{B}\).\N\NThe paper concludes (Section 5) with a more detailed study of the case in which \(k\) is a finite field, and relevant examples for coding theory (e.g., generalized Reed-Muller codes) are given. The author points out that this paper was inspired by the notion of \textit{non-cubic} subsets of a finite dimensional \(\mathbb{F}_2\)-vector space used by \textit{R. Livné} [Contemp. Math. 67, 247--261 (1987; Zbl 0621.14019)] in a criterion to prove that the semi-simplifications of two 2-adic Galois representations are isomorphic. Therefore, the results of this paper could also be useful in representation theory.

Cites work

This page was built for publication: Algebraic notes on testing sets for lower and upper grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6953032)