In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(\mathcal{X}, \mathcal{P}, D)$ over an algebraic curve $\mathcal{X}$ is a vector space associated to evaluations on $\mathcal{P}$ of functions in the Riemann-Roch space $L_\mathcal{X}(D)$. The problem of testing proximity to an error-correcting code $C$ consists in distinguishing between the case where an input word, given as an oracle, belongs to $C$ and the one where it is far from every codeword of $C$. AG codes are good candidates to construct short proof systems, but there exists no efficient proximity tests for them. We aim to fill this gap. We construct an Interactive Oracle Proof of Proximity (IOPP) for some families of AG codes by generalizing an IOPP for Reed-Solomon codes introduced by Ben-Sasson, Bentov, Horesh and Riabzev, known as the FRI protocol. We identify suitable requirements for designing efficient IOPP systems for AG codes. Our approach relies on a neat decomposition of the Riemann-Roch space of any invariant divisor under a group action on a curve into several explicit Riemann-Roch spaces on the quotient curve. We provide sufficient conditions on an AG code $C$ that allow to reduce a proximity testing problem for $C$ to a membership problem for a significantly smaller code $C'$. As concrete instantiations, we study AG codes on Kummer curves and curves in the Hermitian tower. The latter can be defined over polylogarithmic-size alphabet. We specialize the generic AG-IOPP construction to reach linear prover running time and logarithmic verification on Kummer curves, and quasilinear prover time with polylogarithmic verification on the Hermitian tower.

Lattices of compatibly embedded finite fields are useful in computer algebra systems for managing many extensions of a finite field \F_p at once. They can also be used to represent the algebraic closure \bar\F_p, and to represent all finite fields in a standard manner.

We show that with high probability, random rank 1 matrices over a finite field are in (linearly) general position, at least provided their shape k × l is not excessively unbalanced. This translates into saying that the dimension of the *-product of two [n, k] and [n, l] random codes is equal to min(n, kl), as one would have expected. Our work is inspired by a similar result of Cascudo-Cramer-Mirandola-Zémor [4] dealing with *-squares of codes, which it complements, especially regarding applications to the analysis of McEliece-type cryptosystems [5][6]. We also briefly mention the case of higher *-powers, which require to take the Frobenius into account. We then conclude with some open problems.

IfCis a binary linear code, letC〈2〉be the linear code spanned by intersections of pairs of codewords ofC. We construct an asymptotically good family of binary linear codes such that, forCranging in this family,C〈2〉also form an asymptotically good family. For this, we use algebraic-geometry codes, concatenation, and a fair amount of bilinear algebra. More precisely, the two main ingredients used in our construction are, first, a description of the symmetric square of an odd degree extension field in terms only of field operations of small degree, and second, a recent result of Garcia-Stichtenoth-Bassa-Beelen on the number of points of curves on such an odd degree extension field.

We give an upper bound that relates the dimensions of some given number of linear codes, with the minimum distance of their componentwise product. A typical result is as follows: given t linear codes Ciof parameters [n,ki]qwith full support, one can find codewords ci∈ Cisuch that 1 ≤ w(c1*⋯*ct) ≤ max(t-1, n+t-(k1+⋯+kt)).

We give a slight improvement on Xing's lower bound for frameproof codes constructed from algebraic curves. Combined with some additional number-theoretic assumptions (still conjectural) and a concatenation process, this should lead to the existence of a family of binary 2-frameproof codes of asymptotic rate going beyond the up to now best known (non-constructive) lower bound.

Our motivation is the design of space-time coding which is optimal under both maximum likelihood and iterative decoding. We describe the construction of new full-rate space-time codes with non-vanishing determinant that satisfy the genie conditions for iterative probabilistic decoding. The problem combining the genie conditions and the rank criterion is rewritten in terms of a quadratic form. The construction over ¿[i] (the cubic lattice) yields a family of codes defined by Pythagorean triples. The space-time code built over ¿[i] and involving the quaternion algebra (i,5/¿(i)) is referred to as the Aladdin-Pythagoras code. The construction over ¿[j] (the hexagonal lattice) also yields a full-rate non-vanishing determinant code that is suitable for iterative decoding on multiple antenna channels.

In this paper we present an algorithmic approach to the problem of the divisibility of the number of solutions to a system of polynomial equations. Using this method we prove that all binary cyclic codes with two zeros over F2fand minimum distance 5 are quasi-perfect for f les 10. We also present elementary proofs of divisibility results that, in some cases, improve previous results