Fast Computation of Generalized Dedekind Sums

2025-04-22 0 0 1.1MB 11 页 10玖币

侵权投诉

Preston Tranbarger

prestontranbarger@tamu.edu

Department of Mathematics

Texas A&M University

College Station, TX 77843-3368, U.S.A.

Jessica Wang

jwang22@wpi.edu

Department of Mathematical Sciences

Worcester Polytechnic Institute

Worcester, MA 01609-2280, U.S.A.

Abstract

We construct an algorithm that reduces the complexity for computing generalized Dedekind

sums from exponential to polynomial time. We do so by using an eﬃcient word rewriting process

in group theory.

1 Introduction and Main Result

The classical Dedekind sum is well-studied both inside and outside of number theory due to its

connections with the Dedekind eta function and its applications in topology and combinatorial

geometry. For more background on classical Dedekind sums, we refer the reader to [RG72].

Let hand kbe coprime integers with k > 0.The classical Dedekind sum is deﬁned as

s(h, k) =

n=1

B1n

kB1hn

k,

where B1(x) is the ﬁrst Bernoulli function

B1(x) = (0,if x∈Z

x− bxc − 1

2,otherwise.

The classical Dedekind sum satisﬁes the following reciprocity property ([RG72]):

s(h, k) = −s(k, h) + 1

12h

k+1

hk +k

h−1

Using the deﬁnition of classical Dedekind sum, it is readily seen that it can be computed in O(k)

time. However, one can obtain an O(log(k)) time algorithm to compute the classical Dedekind sum

using the reciprocity property ([BR15]).

The generalized Dedekind sum associated with newform Eisenstein series was introduced by

Stucker, Vennos, and Young in [SVY20]. Since then, various aspects of generalized Dedekind sums

have been studied, including the kernel ([NRY21], [LVBY21]), the image ([Maj22]), and their general

behaviour ([DG20]).

arXiv:2210.01172v1 [math.NT] 3 Oct 2022

Deﬁnition 1.1. Let γ=a b

c d ∈Γ0(q1q2)with primitive Dirichlet characters χ1, χ2and respective

conductors q1, q2.Let q1, q2>1and χ1χ2(−1) = 1,then

Sχ1, χ2a b

c d=

j=1

i=1 χ2(j)χ1(i)B1j

cB1n

+aj

c.

The generalized Dedekind sum has the following crossed homomorphism property.

Lemma 1.2 (Crossed Homomorphism Property [SVY20]).Let γ1, γ2∈Γ0(q1q2).Then

Sχ1,χ2(γ1γ2) = Sχ1,χ2(γ1) + ψ(γ1)Sχ1,χ2(γ2),

where ψa b

c d =χ1χ2(d).

Remark. In Lemma 1.2, ψ(γ)is trivial on Γ1(q1q2),so Sχ1,χ2may be viewed as an element of

Hom(Γ1(q1q2),C).

Note that it requires O(cq1) time to compute a generalized Dedekind sum from the deﬁnition.

Similar to the classical Dedekind sums, we are interested in constructing a faster algorithm. Instead

of using the reciprocity property, we provide an alternative approach using a word-rewriting process.

Theorem 1.3. Given primitive Dirichlet characters χ1, χ2and respective conductors q1, q2>1

such that χ1χ2(−1) = 1.Let γ=a b

c d ∈Γ0(q1q2). For ﬁxed q1, q2, the time complexity of ﬁnding

Sχ1,χ2(γ)as a function of γis O(log(c)).

Remark. The algorithm for Theorem 1.3 can be found in Section 3.1. We give the speciﬁc details

of our model of computation in Section 3.2.

Before diving into the technicalities of the algorithm, we provide the reader with a general

outline. Given γ∈Γ1(q1q2)<SL2(Z) written as a word in the generators of SL2(Z), we can apply

the Reidemeister rewriting process to express it as a word in the elements of a particular generating

set of Γ1(q1q2). By precomputing the Dedekind sum of each element of this generating set, we

can use Lemma 1.2 to compute any Dedekind sum. However, in using the Reidemeister rewriting

process, the length of the word can be exponentially large in terms of the logarithms of the entries of

γ. Therefore, to achieve the polynomial time in Theorem 1.3, we modify the Reidemeister rewriting

process, as in Theorem 2.10 below, to collect the exponents of successive letters in the rewritten

word. In the speciﬁc case of Γ1(q1q2),we develop a useful identity in Lemma 2.15 to ensure a ﬁnite

alphabet.

2 Preliminaries

2.1 General Preliminaries

In this section we will deﬁne some general group theoretic deﬁnitions and results which will aid in

the construction of the algorithm. For the rest of this subsection, we let Gbe a ﬁnitely generated

group and Hbe a subgroup of G. We will work with speciﬁc groups in Section 2.2.

Deﬁnition 2.1. We say Tis a right transversal of Hin Gif each right coset of Hin Gcontains

exactly one element of T. Moreover, Tmust contain the identity.

Note that a transversal diﬀers from an arbitrary set of coset representatives in that it must

contain an identity. This fact proves to be essential for later preliminaries.

Deﬁnition 2.2. Given a right transversal Tof Hin G, a right coset representative function for

Tis a mapping: G→ T via g7→ g, where gis the unique element in Tsuch that Hg =Hg.

We present a simple lemma which will be used repeatedly throughout this paper.

Lemma 2.3. Given a right transversal of Hin Gand a, b ∈G,

ab =ab.

Proof. By Deﬁnition 2.2, H(ab) = H(ab)=(Ha)b= (Ha)b=H(ab) = H(ab).

We continue by deﬁning an important function and exploring some of its properties.

Deﬁnition 2.4. Given a right transversal of Hin Gand a, b ∈G, we deﬁne

U(a, b) = ab(ab)−1.

Lemma 2.5. Given a right transversal of Hin Gand a, b ∈G, then U(a, b)∈H.

Proof. By Deﬁnition 2.2, Hab =Hab, thus Hab(ab)−1=H, so ab(ab)−1∈H.

Given a ﬁnite set of generators for a group, we use the information thus far to describe a set of

generators for a given subgroup.

Lemma 2.6 (Schreier’s Lemma [MKS04, Theorem 2.7]).Let Sbe a set which ﬁnitely generates G,

and let Tbe a right transversal of Hin G. The set of Schreier generators

{U(t, s) : t∈ T , s ∈ S}

generates H.

Remark. We say a set generates a group if every element in the group can be expressed as a

combination of elements in the set and their inverses.

We now describe a rewriting process.

Theorem 2.7 (Reidemeister Rewriting Process [MKS04, Corollary 2.7.2]).Let G=hg1,· · · , gni.

Let h=g1

q1g2

q2· · · gr

qr∈H(where k=±1) be a word in the gi. Fix a right transversal of Hin G.

Deﬁne the mapping τof the word hby

τ(h) = U(p1, gq1)1U(p2, gq2)2· · · U(pr, gqr)r,

where

pk=(g1

q1g2

q2· · · gk−1

qk−1if k= 1

g1

q1g2

q2· · · gk

qkif k=−1.

Then τ(h) = h, for all h∈H.

The Reidemeister rewriting process allows us to express a word in the generators of Gas a word

in the Schreier generators of H(using Lemma 2.6).

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

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

10 玖币 0人已下载

立即下载

摘要：

FastComputationofGeneralizedDedekindSumsPrestonTranbargerprestontranbarger@tamu.eduDepartmentofMathematicsTexasA&MUniversityCollegeStation,TX77843-3368,U.S.A.JessicaWangjwang22@wpi.eduDepartmentofMathematicalSciencesWorcesterPolytechnicInstituteWorcester,MA01609-2280,U.S.A.AbstractWeconstructanalgor...

展开>> 收起<<

Fast Computation of Generalized Dedekind Sums.pdf

共11页,预览3页

还剩页未读，继续阅读

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

Fast Computation of Generalized Dedekind Sums

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: