SUM AND DIFFERENCE SETS IN GENERALIZED DIHEDRAL GROUPS RUBEN ASCOLI JUSTIN CHEIGH GUILHERME ZEUS DANTAS E MOURA RYAN JEONG ANDREW KEISLING ASTRID LILLY STEVEN J. MILLER PRAKOD NGAMLAMAI MATTHEW PHANG

2025-05-02 0 0 579.24KB 22 页 10玖币
侵权投诉
SUM AND DIFFERENCE SETS IN GENERALIZED DIHEDRAL GROUPS
RUBEN ASCOLI, JUSTIN CHEIGH, GUILHERME ZEUS DANTAS E MOURA, RYAN JEONG, ANDREW
KEISLING, ASTRID LILLY, STEVEN J. MILLER, PRAKOD NGAMLAMAI, MATTHEW PHANG
Abstract. Given a group G, we say that a set A⊆Ghas more sums than differences (MSTD) if
|A+A|>|A−A|, has more differences than sums (MDTS) if |A+A|<|A−A|, or is sum-difference
balanced if |A+A|=|A−A|. A problem of recent interest has been to understand the frequencies
of these type of subsets.
The seventh author and Vissuet studied the problem for arbitrary finite groups Gand proved
that almost all subsets A⊆Gare sum-difference balanced as |G|→∞. For the dihedral group
D2n, they conjectured that of the remaining sets, most are MSTD, i.e., there are more MSTD sets
than MDTS sets. Some progress on this conjecture was made by Haviland et al. in 2020, when
they introduced the idea of partitioning the subsets by size: if, for each m, there are more MSTD
subsets of D2nof size mthan MDTS subsets of size m, then the conjecture follows.
We extend the conjecture to generalized dihedral groups D=Z2nG, where Gis an abelian group
of size nand the nonidentity element of Z2acts by inversion. We make further progress on the
conjecture by considering subsets with a fixed number of rotations and reflections. By bounding
the expected number of overlapping sums, we show that the collection SD,m of subsets of the
generalized dihedral group Dof size mhas more MSTD sets than MDTS sets when 6 ≤m≤cj√n
for cj= 1.3229/√111 + 5j, where jis the number of elements in Gwith order at most 2. We
also analyze the expectation for |A+A|and |A−A|for A⊆D2n, proving an explicit formula for
|A−A|when nis prime.
1. Introduction and Main Results
Given a set of Aintegers, the sumset and difference set of Aare defined as
A+A={a1+a2:a1, a2∈A}and A−A={a1−a2:a1, a2∈A}.(1)
These elementary operations are fundamental in additive number theory. A natural problem of
recent interest has been to understand the relative sizes of the sum and difference sets of sets A.
Definition 1.1. We say that a set Ahas more sums than differences (MSTD) if |A+A|>
|A−A|; has more differences than sums (MDTS) if |A+A|<|A−A|; or is sum-difference
balanced if |A+A|=|A−A|.
We intuitively expect most sets to be MDTS since addition is commutative and subtraction is
not. Nevertheless, MSTD subsets of integers exist. Nathanson detailed in [Nat07a] the history of
the problem, and attributed to John Conway the first recorded example of an MSTD subset of
integers, {0,2,3,4,7,11,12,14}. Martin and O’Bryant proved in [MO07] that the proportion of
the 2nsubsets Aof {0,1, . . . , n −1}which are MSTD is bounded below by a positive value for all
n≥15. They proved this by controlling the “fringe” elements of A, those close to 0 and n−1,
which have the most influence over whether elements are missing from the sum and difference
sets. In [Zha11], Zhao gave a deterministic algorithm to compute the limit of the ratio of MSTD
subsets of {0,1, . . . , n−1}as ngoes to infinity and found that this ratio is at least 4.28×10−4. For
Date: October 4, 2022.
2020 Mathematics Subject Classification. 11P99, 05B10.
Key words and phrases. More Sums Than Differences, Dihedral Group, Generalized Dihedral Group.
This work was supported by NSF grant DMS1947438, Williams College, and Harvey Mudd College.
1
arXiv:2210.00669v1 [math.NT] 3 Oct 2022
2 ASCOLI, CHEIGH, DANTAS E MOURA, JEONG, KEISLING, LILLY, MILLER, NGAMLAMAI, PHANG
more on the problem of MSTD sets in the integers, see also [Heg07] and [Nat07b] for constructive
examples of infinite families of MSTD sets, [MOS10] and [Zha10a] for non-constructive proofs of
existence of infinite families of MSTD sets, and [HM09] and [HM13] for an analysis of sets with
each integer from 0 to n−1 included with probability cn−δ.
More recently, several authors have examined analogous problems for groups Gother than the
integers. For example, Do, Kulkarni, Moon, Wellens, Wilcox, and the seventh author studied in
[DKMMWW15] the analogous problem for higher-dimensional integer lattices.
For finite groups, although the usual notation for the operation of the group is multiplication, we
match the notation from previous work and define, for a subset A⊆G, its sumset and difference
set as
A+A={a1a2:a1, a2∈A}and A−A={a1a−1
2:a1, a2∈A}.(2)
Definition 1.1 of MSTD, MDTS, and sum-difference balanced sets apply in this context.
The approaches used to study MSTD subsets of integers do not generalize for MSTD subsets of
finite groups due to the lack of fringes. Zhao proved asymptotics for numbers of MSTD subsets
of finite abelian groups as the size of the group goes to infinity in [Zha10b]. The seventh author
and Vissuet examined the problem for arbitrary finite groups G, also with the size of the group
going to infinity, and proved Theorem 1.2.
Theorem 1.2 ([MV14]).Let {Gn}be a sequence of finite groups, not necessarily abelian, with
|Gn|→∞. Let Anbe a uniformly chosen random subset of Gn. Then P[An+An=An−An=
Gn]→1as n→ ∞. In other words, as the size of the finite groups increases without bound,
almost all subsets are balanced (with sumset and difference set equalling the entire group).
Furthermore, for the case of dihedral groups D2n, they proposed Conjecture 1.3.
Conjecture 1.3 ([MV14]).Let n≥3be an integer. There are more MSTD subsets of D2nthan
MDTS subsets of D2n.
Given a set A⊆D2n=hr, s |rn, s2, rsrsi, define R(resp. F) as the set of elements of Aof the
form ri(resp. ris), called rotation elements (resp. flip elements). Hence, A=R∪F. Then, we
can write
A+A= (R+R)∪(F+F)∪(R+F)∪(−R+F),
A−A= (R−R)∪(F+F)∪(R+F).(3)
Intuition for Conjecture 1.3 comes from noting that F+Fand R+Fcontribute to both A+A
and A−A;R+Rand −R+Fcontribute only to A+A; and R−Rcontributes only to A−A.
In 2020, Haviland, Kim, Lˆam, Lentfer, Trejos Su´ares, and the seventh author made progress
towards Conjecture 1.3 by partitioning subsets of D2nby size. They proposed Conjecture 1.4 as
a means of proving Conjecture 1.3.
Conjecture 1.4 ([HKLLMT20]).Let n≥3be an integer, and let S2n,m denote the collection of
subsets of D2nof size m. For any m≤2n,S2n,m has at least as many MSTD sets as MDTS sets.
They showed that Conjecture 1.4 holds for m= 2, which we reproduce in this paper, and we
also extend their approach to m= 3. They also showed that Conjecture 1.4 holds for m > n
by showing that all sets in S2n,m are sum-difference balanced. We prove this result in this paper,
using Lemma 1.5. These results are proved in Section 2.
Lemma 1.5. Let n≥3be an integer, and let A⊆D2n. Let R(resp. F) be the subset of rotations
(resp. flips) in A. Suppose that |F|>n
2or |R|>n
2. Then, Acannot be MDTS.
SUM AND DIFFERENCE SETS IN GENERALIZED DIHEDRAL GROUPS 3
Furthermore, we extend Conjecture 1.3 as follows. A generalized dihedral group is given by
D=Z2nG, where Gis any abelian group and where the nonidentity element of Z2acts on Gby
inversion.
Conjecture 1.6. Let Gbe an abelian group with at least one element of order 3or greater, and
let D=Z2nGbe the corresponding generalized dihedral group. Then, there are more MSTD
subsets of Dthan MDTS subsets of D.
Conjecture 1.3 is a special case of Conjecture 1.6, with G=Zn. We also state Conjecture 1.7,
analogous to Conjecture 1.4.
Conjecture 1.7. Let Dbe a generalized dihedral group of size 2n, and let SD,m denote the collec-
tion of subsets of Dof size m. For any m≤2n,SD,m has at least as many MSTD sets as MDTS
sets.
The version of Lemma 1.5 that we prove in Section 2deals with the generalized dihedral group.
In Section 3, we prove our main theorem, verifying Conjecture 1.7 for the case of m≤cj√n,
where cjis a constant (independent of n) depending only on the quantity j, the number of elements
of order at most 2 in the abelian group G. More explicitly, we show the following.
Theorem 1.8. Let D=Z2nGbe a generalized dihedral group of size 2n. Let SD,m denote the
collection of subsets of Dof size m, and let jdenote the number of elements in Gwith order at
most 2. If 6≤m≤cj√n, where cj= 1.3229/√111 + 5j, then there are more MSTD sets than
MDTS sets in SD,m.
See Section 3the proof of this result and two related theorems. We also extend these results to
the dihedral group on finitely generated abelian groups in Section 3.3.
Next, in Section 4, we discuss the following result about the expected size of |A−A|when Ais
a randomly chosen set in S2n,m, the collection of subsets of D2nof size m.
Theorem 1.9. If nis prime, and Ais chosen uniformly at random from S2n,m, then
E[|A−A|]=2n−nm2mn
m+ 2n(n−1)n−m−1
m−1
m2n
m−n2(n−1)
2n
m
m−1
X
k=1 n+k−m−1
m−k−1n−k−1
k−1
k(m−k).(4)
Finally, in Section 5, we discuss directions for further research.
2. Direct Analysis
2.1. Small Subsets. For the case of the usual dihedral group D2n, we have the following two
results.
Lemma 2.1 ([HKLLMT20]).Let n≥3, and let S2n,2denote the collection of subsets of D2nof
size 2. Then, S2n,2has strictly more MSTD sets than MDTS sets.
Lemma 2.2. Let n≥3, and let S2n,3denote the collection of subsets of D2nof size 3. Then,
S2n,3has strictly more MSTD sets than MDTS sets.
The proofs for both these lemmas use basic and somewhat tedious casework; they can be found
in Appendix A.
Similar results for the generalized dihedral group likely follow from similar arguments.
4 ASCOLI, CHEIGH, DANTAS E MOURA, JEONG, KEISLING, LILLY, MILLER, NGAMLAMAI, PHANG
2.2. Large Subsets. We consider what happens when mgets close to n. Here we can prove a
result for any generalized dihedral group. For the rest of this section, let Gbe a finite abelian
group of size n. Recall that the generalized dihedral group is given by D=Z2nG, where the
nonidentity element of Z2acts on Gby inversion. Note that |D|= 2n. Writing an element of the
group Das (z, g) where z∈ {0,1}and g∈G, we write RDto mean the subset of Dconsisting of
elements with z= 0 and FDto mean the subset of Dconsisting of elements with z= 1. Note that
|RD|=|FD|=n. For the case where D=D2n=Z2n Znis the usual dihedral group, RDand FD
are the sets of rotations and flips, respectively; out of convenience, we will use these terms for the
general case as well.
It turns out that having m > n ensures that Ais balanced.
Lemma 2.3. Let Dbe a generalized dihedral group of size 2n. Let A⊆D, and let R=A∩RD
and F=A∩FD. If max(|R|,|F|)> n/2, then RD⊆A+Aand RD⊆A−A.
Proof. Let Lbe the larger of Rand F, and define LD=RDif L=Rand LD=FDif L=F.
For each rotation r∈RD, define rL−1={r`−1|`∈L}and rL ={r` |`∈L}. Note that
|rL−1|=|rL|=|L|> n/2, and rL−1,rL,Lare subsets of the set LDwhich has size n. Hence, by
the inclusion–exclusion principle, L∩rL−1and L∩rL are nonempty. Thus, r∈L+L⊆A+A
and r∈L−L⊆A−A.
Therefore, as desired, RD⊆A+Aand RD⊆A−A.
Remark 1.Note Lemma 2.3 implies if max(|R|,|F|)> n/2, then Ais not MDTS. This follows from
the discussion after the statement of Conjecture 1.3 (which we explicitly extend to the general
dihedral group case in Section 3). For a set to be MDTS, R−Rmust contribute rotations to
A−Athat the set A+Adoes not have. But here we have shown that if max(|R|,|F|)> n/2,
then A+Ahas all the rotations.
Lemma 2.4. Let Dbe a generalized dihedral group of size 2n, and let A⊆Dwith |A|=m. If
m > n, then A+A=A−A=D.
Proof. Let R(resp. F) be the subset of rotations (resp. flips) in A; hence A=R∪F. Let L, S
be the larger and smaller of Rand F, respectively. Define |L|=n1,|S|=n2for n1+n2=m > n.
Thus, n1> n/2.
By Lemma 2.3, we have that RD⊆A+Aand RD⊆A−A.
For each flip f∈FD, define fL−1={f`−1|`∈L}and fL ={f` |`∈L}.
Note that |fL−1|=|fL|=|L|=n1,|S|=n2, and fL−1, fL, S are subsets of SD, which has
size n<n1+n2. Hence, by the inclusion–exclusion principle, f L−1∪Sand fL ∪Sare nonempty.
Thus, f∈S+L⊆A+Aand f∈S−L⊆A−A. Therefore, FD⊆A+Aand FD⊆A−A.
Thus, we have RD, FD⊆A+Aand RD, FD⊆A−A, which imply A+A=A−A=D.
3. Collision Analysis
Let Gbe a finite abelian group of size n, written multiplicatively. Recall that the generalized
dihedral group is given by D=Z2nG, where the nonidentity element of Z2acts on Gby inversion.
This section is dedicated to proving the following.
Theorem 1.8. Let D=Z2nGbe a generalized dihedral group of size 2n. Let SD,m denote the
collection of subsets of Dof size m, and let jdenote the number of elements in Gwith order at
most 2. If 6≤m≤cj√n, where cj= 1.3229/√111 + 5j, then there are more MSTD sets than
MDTS sets in SD,m.
Note that the theorem is only useful when cj√n≥6, or n≥(6/cj)2.
SUM AND DIFFERENCE SETS IN GENERALIZED DIHEDRAL GROUPS 5
If nis arbitrarily large and jis a constant compared to n, we can make a stronger statement:
we can replace cjin the above theorem with a constant arbitrarily close to q2/7≈0.5345.
Specifically, we have the following.
Theorem 3.1. For fixed jand  > 0, there exists nj, with the following property. Let Gbe an
abelian group of size n≥nj, with at most jelements of order 2or 1. Then with Dand SD,m
defined as in Theorem 1.8, we have that if 6≤m≤q2/7−√n, then there are more MSTD
sets than MDTS sets in SD,m.
We can give a stronger, more general statement on the proportion of MSTD sets in SD,m if m
is large and also bounded above by a (smaller) constant times √n.
Theorem 3.2. Let D, j, and SD,m be defined as in Theorem 1.8. For any  > 0, there exist m
and c,j such that if m≤m≤c,j√n, the proportion of MSTD sets in SD,m is at least 1−.
Here mand c,j are independent of n, but similarly to before, this theorem is only useful when
n≥(m/c,j)2.
Remark 2.In practice, Theorems 1.8 and 3.2 are most useful if jis essentially a constant compared
to n. This is indeed the case for the original dihedral group D2n=Z2n Zn, where j= 1 when
nis odd and j= 2 when nis even, yielding cj≥0.12. The family of original dihedral groups is
also a good example of how to use Theorem 3.1: we can apply that theorem with j= 2 and
arbitrarily small to get that for large enough dihedral groups, we can get the coefficient of the √n
in the theorem to be very close to q2/7, which is a significant improvement over 0.12.
However, these theorems are not useful when, for example, G=Z2×. . . ×Z2×Z3. Here G
does have an element of order at least 3, so Conjecture 1.6 applies, but we have j=n/3, which
is too large for Theorems 1.8 and 3.2 to apply to any values of m. In fact, if j≥n/100, then
n≤(6/cj)2, and Theorem 1.8 does not apply to any values of m.
We first prove Theorem 1.8 here. Then, in Subection 3.1 we demonstrate Theorems 3.1 and 3.2.
Recall the definitions of RDand FDfrom Section 2.2. Note that any element in FDhas order
2 in D. Furthermore, any element in RDhas order at most 2 in Dif and only if it has order at
most 2 in G.
We begin with a set Awith size mand count the number of elements in A+Aand A−A. In
this count, we will make a naive assumption: there are no overlaps between sums and differences
that we do not expect to overlap. Decompose Ainto the union of the set of rotations R=A∩RD
of and the set of flips F=A∩FD, and define k=|F|. We have:
A+A= (R+F)∪(F+R)∪(R+R)∪(F+F);
A−A= (R−F)∪(F−R)∪(R−R)∪(F−F) (5)
Consider first the flips in A+Aand A−A. In A+A, these are in R+Fand F+R. Note
that we do not expect a lot of overlap in general; for a rotation (0, g1)∈Rand a flip (1, g2)∈F,
(0, g1)·(1, g2) = (1, g1g2) does not equal (1, g2)·(0, g1) = (1, g2g−1
1) unless g1has order 1 or 2
in G. On the other hand, for the flips in A−A, we have R−F=F−R. This is because
(0, g1)·(1, g2)−1= (0, g1)·(1, g2) = (1, g1g2), and (1, g2)·(0, g1)−1= (1, g2)·(0, g−1
1) = (1, g1g2), so
these two are the same. There are m−krotations and kflips in A, so we thus expect the flips to
contribute 2(m−k)kto A+Abut only (m−k)kto A−A.
Next, consider the rotations in A+Aand A−A. Begin with F+Fand F−F. Since all flips
have order 2, these are in fact the same set and thus always contribute equally to A+Aand to
A−A. Also note that if k6= 0 (we will treat the k= 0 case later), the identity 1 is contained in
F+Fand F−F.
摘要：

SUMANDDIFFERENCESETSINGENERALIZEDDIHEDRALGROUPSRUBENASCOLI,JUSTINCHEIGH,GUILHERMEZEUSDANTASEMOURA,RYANJEONG,ANDREWKEISLING,ASTRIDLILLY,STEVENJ.MILLER,PRAKODNGAMLAMAI,MATTHEWPHANGAbstract.GivenagroupG,wesaythatasetAGhasmoresumsthandi erences(MSTD)ifjA+Aj>jAAj,hasmoredi erencesthansums(MDTS)ifjA+Aj

展开>> 收起<<
SUM AND DIFFERENCE SETS IN GENERALIZED DIHEDRAL GROUPS RUBEN ASCOLI JUSTIN CHEIGH GUILHERME ZEUS DANTAS E MOURA RYAN JEONG ANDREW KEISLING ASTRID LILLY STEVEN J. MILLER PRAKOD NGAMLAMAI MATTHEW PHANG.pdf

共22页,预览5页

还剩页未读， 继续阅读

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：22 页 大小：579.24KB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 22
评分 收藏
分享
立即下载
客服
关注