ID: 2210.03789

The VC-dimension of quadratic residues in finite fields

October 7, 2022

View on ArXiv

Similar papers 2

Structural theorems on the distance sets over finite fields

November 28, 2021

83% Match
Doowon Koh, Minh Quy Pham, Thang Pham
Number Theory
Combinatorics

Let $\mathbb{F}_q$ be a finite field of order $q$. Iosevich and Rudnev (2005) proved that for any set $A\subset \mathbb{F}_q^d$, if $|A|\gg q^{\frac{d+1}{2}}$, then the distance set $\Delta(A)$ contains a positive proportion of all distances. Although this result is sharp in odd dimensions, it is conjectured that the right exponent should be $\frac{d}{2}$ in even dimensions. During the last 15 years, only some improvements have been made in two dimensions, and the conjecture ...

Find SimilarView on arXiv

On squares in subsets of finite fields with restrictions on coefficients of basis decomposition

February 21, 2016

83% Match
Mikhail Gabdullin
Number Theory

We consider the linear vector space formed by the elements of the finite fields $\mathbb{F}_q$ with $q=p^r$ over $\mathbb{F}_p$. Let ${a_1,\ldots,a_r}$ be a basis of this space. Then the elements $x$ of $\mathbb{F}_q$ have a unique representation in the form $\sum_{j=1}^r c_ja_j$ with $c_j\in\mathbb{F}_p$. Let $D$ be a subset of $\mathbb{F}_p$. We consider the set $W_D$ of elements of $\mathbb{F}_q$ such that $c_j\in D$ for all $j=1,\ldots,r$. We give an estimate for the numb...

Find SimilarView on arXiv

On quadratic residue codes and hyperelliptic curves

September 20, 2006

83% Match
David Joyner
Combinatorics
Information Theory
Algebraic Geometry
Information Theory
Number Theory

A long standing problem has been to develop "good" binary linear codes to be used for error-correction. This paper investigates in some detail an attack on this problem using a connection between quadratic residue codes and hyperelliptic curves. One question which coding theory is used to attack is: Does there exist a c<2 such that, for all sufficiently large $p$ and all subsets S of GF(p), we have |X_S(GF(p))| < cp?

Find SimilarView on arXiv

Sums and products in finite fields: an integral geometric viewpoint

May 29, 2007

82% Match
Derrick University of Missouri - Columbia Hart, Alex University of Missouri - Columbia Iosevich
Number Theory
Classical Analysis and ODEs

We prove that if $A \subset {\Bbb F}_q$ is such that $$|A|>q^{{1/2}+\frac{1}{2d}},$$ then $${\Bbb F}_q^{*} \subset dA^2=A^2+...+A^2 d \text{times},$$ where $$A^2=\{a \cdot a': a,a' \in A\},$$ and where ${\Bbb F}_q^{*}$ denotes the multiplicative group of the finite field ${\Bbb F}_q$. In particular, we cover ${\Bbb F}_q^{*}$ by $A^2+A^2$ if $|A|>q^{{3/4}}$. Furthermore, we prove that if $$|A| \ge C_{size}^{\frac{1}{d}}q^{{1/2}+\frac{1}{2(2d-1)}},$$ then $$|dA^2| \ge q \cdot \...

Find SimilarView on arXiv

Estimates for the number of rational points on simple abelian varieties over finite fields

June 5, 2019

82% Match
Borys Kadets
Number Theory
Algebraic Geometry

Let $A$ be a simple abelian variety of dimension $g$ over the field $\mathbb{F}_q$. The paper provides improvements on the Weil estimates for the size of $A(\mathbb{F}_q)$. For an arbitrary value of $q$ we prove $(\lfloor(\sqrt{q}-1)^2 \rfloor + 1)^g \leqslant A(\mathbb{F}_q) \leqslant (\lceil(\sqrt{q}+1)^2 \rceil - 1)^{g}$ holds with finitely many exceptions. We compute improved bounds for various small values of $q$. For instance, the Weil bounds for $q=3,4$ give a trivial ...

Find SimilarView on arXiv

On primitive elements in finite fields of low characteristic

December 20, 2014

82% Match
Abhishek Bhowmick, Thái Hoàng Lê
Number Theory
Computational Complexity

We discuss the problem of constructing a small subset of a finite field containing primitive elements of the field. Given a finite field, $\mathbb{F}_{q^n}$, small $q$ and large $n$, we show that the set of all low degree polynomials contains the expected number of primitive elements. The main theorem we prove is a bound for character sums over short intervals in function fields. Our result is unconditional and slightly better than what is known (conditionally under GRH) in...

Find SimilarView on arXiv

Inverse questions for the large sieve

November 24, 2013

82% Match
Ben J. Green, Adam J. Harper
Number Theory

Suppose that an infinite set $A$ occupies at most $\frac{1}{2}(p+1)$ residue classes modulo $p$, for every sufficiently large prime $p$. The squares, or more generally the integer values of any quadratic, are an example of such a set. By the large sieve inequality the number of elements of $A$ that are at most $X$ is $O(X^{1/2})$, and the quadratic examples show that this is sharp. The simplest form of the inverse large sieve problem asks whether they are the only examples. W...

Find SimilarView on arXiv

Sum-product estimates over arbitrary finite fields

May 23, 2018

82% Match
Doowon Koh, Sujin Lee, ... , Shen Chun-Yen
Number Theory

In this paper we prove some results on sum-product estimates over arbitrary finite fields. More precisely, we show that for sufficiently small sets $A\subset \mathbb{F}_q$ we have \[|(A-A)^2+(A-A)^2|\gg |A|^{1+\frac{1}{21}}.\] This can be viewed as the Erd\H{o}s distinct distances problem for Cartesian product sets over arbitrary finite fields. We also prove that \[\max\{|A+A|, |A^2+A^2|\}\gg |A|^{1+\frac{1}{42}}, ~|A+A^2|\gg |A|^{1+\frac{1}{84}}.\]

Find SimilarView on arXiv

Configurations of rectangles in a set in $\mathbb{F}_q^2$

March 21, 2021

82% Match
Doowon Koh, Sujin Lee, ... , Shen Chun-Yen
Combinatorics
Number Theory

Let $\mathbb{F}_q$ be a finite field of order $q$. In this paper, we study the distribution of rectangles in a given set in $\mathbb{F}_q^2$. More precisely, for any $0<\delta\le 1$, we prove that there exists an integer $q_0=q_0(\delta)$ with the following property: if $q\ge q_0$ and $A$ is a multiplicative subgroup of $\mathbb{F}^*_q$ with $|A|\ge q^{2/3}$, then any set $S\subset \mathbb{F}_q^2$ with $|S|\ge \delta q^2$ contains at least $\gg \frac{|S|^4|A|^2}{q^5}$ rectang...

Find SimilarView on arXiv

A note on the Freiman and Balog-Szemeredi-Gowers theorems in finite fields

January 22, 2007

82% Match
Ben Green, Terence Tao
Combinatorics
Number Theory

We obtain quantitative versions of the Balog-Szemeredi-Gowers and Freiman theorems in the model case of a finite field geometry F_2^n, improving the previously known bounds in such theorems. For instance, if A is a subset of F_2^n such that |A+A| <= K|A| (thus A has small additive doubling), we show that there exists an affine subspace V of F_2^n of cardinality |V| >> K^{-O(\sqrt{K})} |A| such that |A \cap V| >> |V|/2K. Under the assumption that A contains at least |A|^3/K qu...

Find SimilarView on arXiv