Source author record

Peter Beelen

Peter Beelen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

27works
7topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2026arXiv

Faster List Decoding of AG Codes

In this article, we present a fast algorithm performing an instance of the Guruswami-Sudan list decoder for algebraic geometry codes. We show that any such code can be decoded in $\tilde{O}(s^2\ell^{ω-1}μ^{ω-1}(n+g) + \ell^ωμ^ω)$ operations in the underlying finite field, where $n$ is the code length, $g$ is the genus of the function field used to construct the code, $s$ is the multiplicity parameter, $\ell$ is the designed list size and $μ$ is the smallest positive element in the Weierstrass semigroup of some chosen place.

preprint2022arXiv

A Combinatorial Approach to the Number of Solutions of Systems of Homogeneous Polynomial Equations over Finite Fields

We give a complete conjectural formula for the number $e_r(d,m)$ of maximum possible ${\mathbb{F}}q$-rational points on a projective algebraic variety defined by $r$ linearly independent homogeneous polynomial equations of degree $d$ in $m+1$ variables with coefficients in the finite field ${\mathbb{F}}q$ with $q$ elements, when $d<q$. It is shown that this formula holds in the affirmative for several values of $r$. In the general case, we give explicit lower and upper bounds for $e_r(d,m)$ and show that they are sometimes attained. Our approach uses a relatively recent result, called the projective footprint bound, together with results from extremal combinatorics such as the Clements-Lindström Theorem and its variants. Applications to the problem of determining the generalized Hamming weights of projective Reed-Muller codes are also included.

preprint2022arXiv

A survey on recursive towers and Ihara's constant

Since Serre gave his famous Harvard lectures in 1985 on various aspects of the theory of algebraic curves defined over a finite field, there have been many developments. In this survey article, an overview will be given on the developments concerning the quantity $A(q)$, known as Ihara's constant. The main focus will be on explicit techniques and in particular recursively defined towers of function fields over a finite field, which have given good lower bounds for Ihara's constant in the past.

preprint2022arXiv

Fast Decoding of AG Codes

We present an efficient list decoding algorithm in the style of Guruswami-Sudan for algebraic geometry codes. Our decoder can decode any such code using $\tilde{\mathcal O}(s\ell^ωμ^{ω-1}(n+g))$ operations in the underlying finite field, where $n$ is the code length, $g$ is the genus of the function field used to construct the code, $s$ is the multiplicity parameter, $\ell$ is the designed list size and $μ$ is the smallest positive element in the Weierstrass semigroup at some chosen place; the "soft-O" notation $\tilde{\mathcal O}(\cdot)$ is similar to the "big-O" notation ${\mathcal O}(\cdot)$, but ignores logarithmic factors. For the interpolation step, which constitutes the computational bottleneck of our approach, we use known algorithms for univariate polynomial matrices, while the root-finding step is solved using existing algorithms for root-finding over univariate power series.

preprint2022arXiv

On the constant $D(q)$ defined by Homma

Let $\mathcal{X}$ be a projective, irreducible, nonsingular algebraic curve over the finite field $\mathbb{F}_q$ with $q$ elements and let $|\mathcal{X}(\mathbb{F}_q)|$ and $g(\mathcal X)$ be its number of rational points and genus respectively. The Ihara constant $A(q)$ has been intensively studied during the last decades, and it is defined as the limit superior of $|\mathcal{X}(\mathbb{F}_q)|/g(\mathcal X)$ as the genus of $\mathcal X$ goes to infinity. In 2012 Homma defined an analogue $D(q)$ of $A(q)$, where the nonsingularity of $\mathcal X$ is dropped and $g(\mathcal X)$ is replaced with the degree of $\mathcal X$. We will call $D(q)$ Homma's constant. In this paper, upper and lower bounds for the value of $D(q)$ are found.

preprint2022arXiv

Twisted Reed-Solomon Codes

In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed-Solomon codes. Whereas Reed-Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results.

preprint2020arXiv

A bound for the number of points of space curves over finite fields

For a non-degenerate irreducible curve $C$ of degree $d$ in $\mathbb{P}^3$ over $\mathbb{F}_q$, we prove that the number $N_q(C)$ of $\mathbb{F}_q$-rational points of $C$ satisfies the inequality $N_q(C) \leq (d-2)q+1$. Our result improves the previous bound $N_q(C) \leq (d-1)q+1$ obtained by Homma in 2012 and leads to a natural conjecture generalizing Sziklai's bound for the number of points of plane curves over finite fields.

preprint2020arXiv

Fast Encoding of AG Codes over $C_{ab}$ Curves

We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called $C_{ab}$ curves, as well as algorithms for inverting the encoding map, which we call "unencoding". Some $C_{ab}$ curves have many points or are even maximal, e.g. the Hermitian curve. Our encoding resp. unencoding algorithms have complexity $\tilde{O}(n^{3/2})$ resp. $\tilde{O}(qn)$ for AG codes over any $C_{ab}$ curve satisfying very mild assumptions, where $n$ is the code length and $q$ the base field size, and $\tilde{O}$ ignores constants and logarithmic factors in the estimate. For codes over curves whose evaluation points lie on a grid-like structure, notably the Hermitian curve and norm-trace curves, we show that our algorithms have quasi-linear time complexity $\tilde{O}(n)$ for both operations. For infinite families of curves whose number of points is a constant factor away from the Hasse--Weil bound, our encoding algorithm has complexity $\tilde{O}(n^{5/4})$ while unencoding has $\tilde{O}(n^{3/2})$.

preprint2020arXiv

Maximum number of points on intersection of a cubic surface and a non-degenerate Hermitian surface

In 1991 Sørensen proposed a conjecture for the maximum number of points on the intersection of a surface of degree $d$ and a non-degenerate Hermitian surface in $\PP^3(\Fqt)$. The conjecture was proven to be true by Edoukou in the case when $d=2$. In this paper, we prove that the conjecture is true for $d=3$ and $q \ge 8$. We further determine the second highest number of rational points on the intersection of a cubic surface and a non-degenerate Hermitian surface. Finally, we classify all the cubic surfaces that admit the highest and second highest number of points in common with a non-degenerate Hermitian surface. This classifications disproves one of the conjectures proposed by Edoukou, Ling and Xing.

preprint2020arXiv

Point-line incidence on Grassmannians and majority logic decoding of Grassmann codes

In this article, we consider the decoding problem of Grassmann codes using majority logic. We show that for two points of the Grassmannian, there exists a canonical path between these points once a complete flag is fixed. These paths are used to construct a large set of parity checks orthogonal on a coordinate of the code, resulting in a majority decoding algorithm.

preprint2020arXiv

Weierstrass semigroups on the Skabelund maximal curve

In 2017, D. Skabelund constructed a maximal curve over $\mathbb{F}_{q^4}$ as a cyclic cover of the Suzuki curve. In this paper we explicitly determine the structure of the Weierstrass semigroup at any point $P$ of the Skabelund curve. We show that its Weierstrass points are precisely the $\mathbb{F}_{q^4}$-rational points. Also we show that among the Weierstrass points, two types of Weierstrass semigroup occur: one for the $\mathbb{F}_q$-rational points, one for the remaining $\mathbb{F}_{q^4}$-rational points. For each of these two types its Apéry set is computed as well as a set of generators.

preprint2016arXiv

Good families of Drinfeld modular curves

In this paper we investigate examples of good and optimal Drinfeld modular towers of function fields. Surprisingly, the optimality of these towers has not been investigated in full detail in the literature. We also give an algorithmic approach on how to obtain explicit defining equations for some of these towers and in particular give a new explicit example of an optimal tower over a quadratic finite field.

preprint2015arXiv

Linear Codes associated to Determinantal Varieties

We consider a class of linear codes associated to projective algebraic varieties defined by the vanishing of minors of a fixed size of a generic matrix. It is seen that the resulting code has only a small number of distinct weights. The case of varieties defined by the vanishing of 2 x 2 minors is considered in some detail. Here we obtain the complete weight distribution. Moreover, several generalized Hamming weights are determined explicitly and it is shown that the first few of them coincide with the distinct nonzero weights. One of the tools used is to determine the maximum possible number of matrices of rank 1 in a linear space of matrices of a given dimension over a finite field. In particular, we determine the structure and the maximum possible dimension of linear spaces of matrices in which every nonzero matrix has rank 1.

preprint2015arXiv

Sub-quadratic Decoding of One-point Hermitian Codes

We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realisation of the Guruswami-Sudan algorithm by using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimisation. The second is a Power decoding algorithm: an extension of classical key equation decoding which gives a probabilistic decoding algorithm up to the Sudan radius. We show how the resulting key equations can be solved by the same methods from computer algebra, yielding similar asymptotic complexities.

preprint2013arXiv

Galois Towers over Non-prime Finite Fields

In this paper we construct Galois towers with good asymptotic properties over any non-prime finite field $\mathbb F_{\ell}$; i.e., we construct sequences of function fields $\mathcal{N}=(N_1 \subset N_2 \subset \cdots)$ over $\mathbb F_{\ell}$ of increasing genus, such that all the extensions $N_i/N_1$ are Galois extensions and the number of rational places of these function fields grows linearly with the genus. The limits of the towers satisfy the same lower bounds as the best currently known lower bounds for the Ihara constant for non-prime finite fields. Towers with these properties are important for applications in various fields including coding theory and cryptography.

preprint2013arXiv

Good Towers of Function Fields

In this paper, we will give an overview of known and new techniques on how one can obtain explicit equations for candidates of good towers of function fields. The techniques are founded in modular theory (both the classical modular theory and the Drinfeld modular theory). In the classical modular setup, optimal towers can be obtained, while in the Drinfeld modular setup, good towers over any non-prime field may be found. We illustrate the theory with several examples, thus explaining some known towers as well as giving new examples of good explicitly defined towers of function fields.

preprint2013arXiv

On Rational-Interpolation Based List-Decoding and List-Decoding Binary Goppa Codes

We derive the Wu list-decoding algorithm for Generalised Reed-Solomon (GRS) codes by using Gröbner bases over modules and the Euclidean algorithm (EA) as the initial algorithm instead of the Berlekamp-Massey algorithm (BMA). We present a novel method for constructing the interpolation polynomial fast. We give a new application of the Wu list decoder by decoding irreducible binary Goppa codes up to the binary Johnson radius. Finally, we point out a connection between the governing equations of the Wu algorithm and the Guruswami-Sudan algorithm (GSA), immediately leading to equality in the decoding range and a duality in the choice of parameters needed for decoding, both in the case of GRS codes and in the case of Goppa codes.

preprint2012arXiv

Bounding the number of points on a curve using a generalization of Weierstrass semigroups

In this article we use techniques from coding theory to derive upper bounds for the number of rational places of the function field of an algebraic curve defined over a finite field. The used techniques yield upper bounds if the (generalized) Weierstrass semigroup [P. Beelen, N. Tutaş: A generalization of the Weierstrass semigroup, J. Pure Appl. Algebra, 207(2), 2006] for an $n$-tuple of places is known, even if the exact defining equation of the curve is not known. As shown in examples, this sometimes enables one to get an upper bound for the number of rational places for families of function fields. Our results extend results in [O. Geil, R. Matsumoto: Bounding the number of $\mathbb{F}_q$-rational places in algebraic function fields using Weierstrass semigroups. Pure Appl. Algebra, 213(6), 2009].

preprint2011arXiv

Duals of Affine Grassmann Codes and their Relatives

Affine Grassmann codes are a variant of generalized Reed-Muller codes and are closely related to Grassmann codes. These codes were introduced in a recent work [2]. Here we consider, more generally, affine Grassmann codes of a given level. We explicitly determine the dual of an affine Grassmann code of any level and compute its minimum distance. Further, we ameliorate the results of [2] concerning the automorphism group of affine Grassmann codes. Finally, we prove that affine Grassmann codes and their duals have the property that they are linear codes generated by their minimum-weight codewords. This provides a clean analogue of a corresponding result for generalized Reed-Muller codes.

preprint2011arXiv

Explicit equations for Drinfeld modular towers

Elaborating on ideas of Elkies, we show how recursive equations for towers of Drinfeld modular curves $(X_0(P^n))_{n\ge 0}$ for $P\in \mathbb F_q[T]$ can be read of directly from the modular polynomial $Φ_P(X,Y)$ and how this naturally leads to recursions of depth two. Although the modular polynomial $Φ_T(X,Y)$ is not known in general, using generators and relations given by Schweizer, we find unreduced recursive equations over $\mathbb F_q(T)$ for the tower $(X_0(T^n))_{n\ge 2}$ and of a small variation of it (its partial Galois closure). Reducing at various primes, one obtains towers over finite fields, which are optimal, i.e., reach the Drinfeld--Vladut bound, over a quadratic extension of the finite field. We give a proof of the optimality of these towers, which is elementary and does not rely on their modular interpretation except at one point. We employ the modular interpretation to determine the splitting field of certain polynomials, which are analogues of the Deuring polynomial. For these towers, the particular case of reduction at the prime $T-1$ corresponds to towers introduced by Elkies and Garcia--Stichtenoth.