THE VC DIMENSION OF QUADRATIC RESIDUES IN FINITE FIELDS BRIAN MCDONALD ANURAG SAHAY AND EMMETT L. WYMAN

2025-05-06 0 0 603.14KB 22 页 10玖币

侵权投诉

THE VC DIMENSION OF QUADRATIC RESIDUES IN

FINITE FIELDS

BRIAN MCDONALD, ANURAG SAHAY, AND EMMETT L. WYMAN

Abstract. We study the Vapnik–Chervonenkis (VC) dimension

of the set of quadratic residues (i.e. squares) in ﬁnite ﬁelds, Fq,

when considered as a subset of the additive group. We conjec-

ture that as q→ ∞, the squares have the maximum possible

VC-dimension, viz. (1 + o(1)) log2q. We prove, using the Weil

bound for multiplicative character sums, that the VC-dimension

is ⩾(1

2+o(1)) log2q. We also provide numerical evidence for

our conjectures. The results generalize to multiplicative subgroups

Γ⊆F×

qof bounded index.

1. Introduction

Consider the setting of an Abelian group written additively. For any

subset, one deﬁnes the Vapnik–Chervonenkis dimension (VC-dimension

for conciseness) of Sas follows.

Deﬁnition 1.1 (VC-dimension in groups).Let (G, +) be an Abelian

group, and let S⊆Gbe an arbitrary subset. We say that Sshatters

Y={y1,··· , yn} ⊆ Gif for any ∅ ⊆ A⊆Y, there is an x∈Gsuch

that

yj∈A⇐⇒ yj∈(S+x)

for 1 ⩽j⩽n. Here, and throughout, we assume that |Y|=nso that

yj̸=ykfor 1 ⩽j < k ⩽n. Further, we deﬁne the VC-dimension of S

to be the cardinality of the largest set Ythat is shattered by S, and

we denote it by VCdimG(S)

Readers familiar with the deﬁnition of VC-dimension in the language

of set systems or classiﬁers (see, e.g., [30, Chapter 6]) should note that

this is the usual notion of VC-dimension relative to the set system PS

of translates of S,

PS={S+x:x∈G},

where S+x=S+{x}={z+x:z∈S}, or equivalently relative to

the classiﬁers

HS={1S+x:x∈G, }

arXiv:2210.03789v2 [math.CO] 31 Jul 2024

THE VC DIMENSION OF QUADRATIC RESIDUES IN FINITE FIELDS 2

where here and throughout, 1S:G→ {0,1}is the indicator function

of the set S. Further, a standard argument shows that VCdimG(S)⩽

log2|G|for every S, where |·| denotes cardinality.

A class of ambient groups of interest to us are the vector spaces over

ﬁnite ﬁelds – i.e., G=Fd

qfor prime power qand some dimension d⩾

1. A speciﬁc instance of this type was considered by the Fitzpatrick,

Iosevich, McDonald, and Wyman [16], where they investigated a circle

in a plane G=F2

q. Another example of this type was considered

by Iosevich, McDonald, and Sun [20] where they considered G=F3

and sets deﬁned using dot products. Since the initial dissemination of

our work, several related works along similar themes as [16, 20] have

appeared [4, 5, 26, 27].

Our objective in this paper is to investigate the VC-dimension of sets

with multiplicative structure in Fq, when considered as subsets of the

additive group (Fq,+). Our particular interest is in the set of quadratic

residues (i.e. squares) Sq⊆Fqgiven by

Sq={x2:x∈F×

q}.

We remark at this point that our analysis can be easily adjusted to

include the number 0 in Sqif the reader desires. For economy of nota-

tion, however, we adopt the point of view that 0 is “half” an element of

Sq, a decision which we shall explain later. Concretely, we mean that

1Sq(y) = 









1 if y=x2, x ∈F×

1/2 if y= 0,

0 otherwise,

where 1Sqis the indicator function of Sq. This requires some modiﬁca-

tion to the meaning of shattering from Deﬁnition 1.1; for our purposes,

it suﬃces to add the extra requirement that the x∈Gsuch that

A=Y∩(Sq+x) satisﬁes x /∈Y.

Another viewpoint on our problem is provided by using graph the-

oretic terminology. In this article, graphs are directed, do not have

multiple edges, and may have loops. We denote graphs also by the let-

ter G, but this should cause no confusion, as the the underlying vertex

set of our graphs shall be Abelian groups. For any vertex v∈G, the

(out)-neighbourhood of vis given by

N(v) = {w∈G:v→win G},

and the VC-dimension of the set family of neighbourhoods is called

the VC-dimension of the graph. This is encapsulated in the following

deﬁnition.

THE VC DIMENSION OF QUADRATIC RESIDUES IN FINITE FIELDS 3

Deﬁnition 1.2 (VC-dimension in graphs).Let G= (V, E) be a di-

rected graph. We say that Eshatters Y={y1,··· , yn} ⊆ Gif for any

∅ ⊆ A⊆Y, there is an x∈Gsuch that

yj∈A⇐⇒ x→yjin G

for 1 ⩽j⩽n. Further, we deﬁne the VC-dimension of G= (V, E) to

the be cardinality of the largest set Ythat is shattered by E, and we

denote it by VCdim′

G(E)

The astute reader will notice that the above generalizes Deﬁnition 1.1

as for a group Gand a subset S⊆G, if we set Eto be the edge-set of

the Cayley (di)graph Cay(G, S), then

VCdimG(S) = VCdim′

G(E).

Thus, if we deﬁne Pq= Cay(Fq,Sq) to be the usual notion of the Paley

(di)graph, we see that the problem we are interested in is exactly the

question of the VC-dimension of Pq. Paley graphs are an important

example of pseudorandom graphs (see, for example, the seminal work

of Chung, Graham, and Wilson [11]).

VC-dimension can be thought of as a measure of complexity when

viewed internally from a structure (e.g., the group structure or the

graph structure). Thus, if a set S⊆Ghas high additive structure, one

might expect a low VC-dimension. Conversely, if Shas low additive

structure, one should expect a high VC-dimension. There are numerous

recent works in the combinatorics literature where the assumption of

bounded VC-dimension delivers strong structure on the involved sets

(see, for example, [2],[31],[17],[18], [23], [1]).

Since Sqis clearly multiplicatively structured, and since one expects

that addition and multiplication in Fqare only loosely correlated due to

the sum-product phenomenon (see, for example, [9],[33],[29], and ref-

erences therein), it is natural to expect that Sqwill have the maximum

possible VC-dimension, log2q. Furthermore, since Pqis pseudorandom,

it is similarly natural to expect that it would have maximum possible

VC-dimension.

To state our expectations in this regard, we introduce two quantities

αqand βq. The former is deﬁned by

αq=VCdimFq(Sq)

log2q.

For the latter, we deﬁne ﬁrst mqto be the largest integer such that all

subsets Y⊆Fqof size |Y|⩽mqare shattered by Sq. Then,

βq=mq

log2q.

THE VC DIMENSION OF QUADRATIC RESIDUES IN FINITE FIELDS 4

The quantity mqis called the testing dimension by some authors (for

example [3] and [28]). It is straightforward to see that 0 ⩽βq⩽αq⩽1.

Finally, we further deﬁne

α= lim sup

q→∞

αq, α = lim inf

q→∞ αq,

β= lim sup

q→∞

βq, β = lim inf

q→∞ βq.(1)

We can now formally state our aforementioned expectation.

Conjecture 1.3. Let αbe as deﬁned in (1). Then, α= 1. In partic-

ular, it follows that α=αand further, that

VCdimFq(Sq) = (1 + o(1)) log2q.

We are not able to prove this conjecture. However, we have partial

progress, in the form of the following theorem.

Theorem 1.4. Let βbe as deﬁned in (1). Then, β⩾1/2. In partic-

ular, for any ϵ > 0, we have that for all q≫ϵ1, and for every subset

Y⊆Fqwith |Y|⩽(1

2−ϵ) log2q, the set of squares Sqshatters Y.

In particular, it is immediate from this theorem that α⩾1/2, and

further that

VCdimFq(Sq)⩾(1

2−ϵ) log2q.

for all q≫ϵ1.

Our results in this regard follow from the broader context where Sq

(which is a multiplicative subgroup of index 2) is replaced by a more

general multiplicative subgroup Γ ⊆F×

q. In particular, recall that since

F×

qis cyclic, for every r|(q−1), F×

qhas exactly one subgroup of index

r, namely the set of rth powers,

Γ(r)={xr:x∈F×

q},

so that Γ(2) =Sq. Further, as with squares, we adopt the point of view

that 0 is a “fuzzy” member of Γ(r)with weight 1/r. In fact, we assume

that for each multiplicative coset tΓ(r)={txr:x∈F×

q}, 0 is a fuzzy

member of tΓ(r)with weight 1/r. That is, for t̸= 0,

1tΓ(r)(y) = 









1 if y∈tΓ(r),

1/r if y= 0,

0 otherwise.

(2)

Analogous to the r= 2 case, we deﬁne

α(r)

q=VCdimFq(Γ(r))

log2q, β(r)

q=m(r)

log2q,

THE VC DIMENSION OF QUADRATIC RESIDUES IN FINITE FIELDS 5

where now m(r)

qis the largest integer such that all subsets Y⊆Fqof

size |Y|⩽m(r)

qare shattered by Γ(r). We further deﬁne

α(r)= lim sup

q→∞

α(r)

q, α(r)= lim inf

q→∞ α(r)

β(r)= lim sup

q→∞

β(r)

q, β(r)= lim inf

q→∞ β(r)

q.(3)

Then, provided that Γ(r)is of bounded index (i.e., r≪1), we expect

the natural generalization of Conjecture 1.3 to hold, and are able to able

to prove the analogous partial progress, with 1/2 replaced by (logr2)/2

Conjecture 1.5. Let α(r)be as deﬁned in (3). Then, α(r)= 1. In

particular, it follows that α(r)=α(r)and further that

VCdimFq(Γ(r)) = (1 + or(1)) log2q.

Theorem 1.6. Let β(r)be as deﬁned in (3). Then, β(r)⩾(logr2)/2.

In particular, for any ϵ > 0, we have that for all q≫r,ϵ 1, and for

every subset Y⊆Fqwith |Y|⩽(1

2−ϵ) logrq, the set of rth powers Γ(r)

shatters Y.

It is clear that Theorem 1.4 is a corollary of this one. We now focus on

this theorem, and provide an overview of its proof. Broadly speaking,

we proceed by showing that Γ(r)shatters Y={y1,··· , yn}provided a

certain expression involving the indicator functions of the multiplicative

cosets tΓ(r)evaluated at yj−xis positive. Then, we Fourier-expand

these indicator functions using the (multiplicative) characters on the

quotient group F×

q/Γ(r). Since F×

qis cyclic, so is \

F×

q/Γ(r), and hence

everything can be written in terms of its generator χr. Upon doing so,

the task reduces to ﬁnding nontrivial bounds for sums of the form

x∈Fq

χr(f(x)),

where f(x) is a polynomial of the form

f(x) =

j=1

(yj−x)kj,

for some 0 ⩽kj< r. At this point, we use the Weil bound for multi-

plicative character sums to upper bound these sums point-wise, which

delivers the result. This method is uniform in the choice of Yprovided

|Y|=nis small enough in terms of q, which is what enables us to con-

trol the quantity β(r). We remark that an averaging argument that is

elementary (relative to the Weil bound, at least) can be used to prove

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

THEVCDIMENSIONOFQUADRATICRESIDUESINFINITEFIELDSBRIANMCDONALD,ANURAGSAHAY,ANDEMMETTL.WYMANAbstract.WestudytheVapnik–Chervonenkis(VC)dimensionofthesetofquadraticresidues(i.e.squares)infinitefields,Fq,whenconsideredasasubsetoftheadditivegroup.Weconjec-turethatasq→∞,thesquareshavethemaximumpossibleVC-di...

展开>> 收起<<

THE VC DIMENSION OF QUADRATIC RESIDUES IN FINITE FIELDS BRIAN MCDONALD ANURAG SAHAY AND EMMETT L. WYMAN.pdf

共22页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

THE VC DIMENSION OF QUADRATIC RESIDUES IN FINITE FIELDS BRIAN MCDONALD ANURAG SAHAY AND EMMETT L. WYMAN

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: