關于k-sum-avoiding子集基數的估計

趙青青

(河海大學文天學院,安徽馬鞍山243031)

關于k-sum-avoiding子集基數的估計

趙青青

(河海大學文天學院,安徽馬鞍山243031)

對sum-avoiding子集進行推廣,對任意正整數k(k≥2),若集合S是A?N的一個子集,且S中任意k個元素的和都不屬于A,則S稱為集合A的k-sum-avoiding子集.估計了當|A|=n時,A的k-sum-avoiding子集S的最大基數.

sum-avoiding子集;最大基數;k-sum-avoiding子集

1 前言和主要結果

若S是集合A?N的一個子集,且S中任意兩個不同元素的和都不屬于A,則S稱為集合A的sum-avoiding子集.

用λ(A)記A的sum-avoiding子集的最大基數,且

1971年,文獻[1]證明了?(n)?n2/5+o(1).2005年,文獻[2]證明了如下結論:

這也是目前最好的上界.文獻[2]證明上界的方法與Behrend在文獻[3]中用到的方法有些類似.同一年,文獻[4]將?(n)的下界改進到lognlogloglogloglogn.

受文獻[5]啟發,本文對sum-avoiding子集進行推廣.對任意正整數k(k≥2),若集合S是A?N的一個子集,且S中任意k個不同元素的和都不屬于A,則S稱為集合A的k-sum-avoiding子集.用λk(A)記A的k-sum-avoiding子集的最大基數,且

對?k(n)的上界進行估計,得到如下結論.

定理1.1對任意正整數k(k≥2),特別地,取k=2,可以得到文獻[2]的結果.

2 引理

引理2.1設正整數d≥2,b1,b2,···,bk為中的k(k≥2)個不同的向量.若

且對每個j(1≤j≤k)都有

則

證明由三角不等式,有

將此不等式推廣到k個向量可得,

上述等號成立當且僅當所有的向量bj(1≤j≤k)共線且滿足各不相同,故上述等號不成立.因此

又因為

故

為整數.因此

引理2.2(Erds-Ginzburg-Ziv定理[6])設n≥1,若a0,a1,···,a2n?2是2n?1個不同整數構成的數列,則一定存在一個子數列ai1,ai2,···,ain,使得

3 定理

引理3.1對任意正整數

證明首先,選取恰當的d,構造集合E?Zd,使得|E|>n,且對于任意有

給定一個正整數r,定義

考慮集合

其中kB={kb:b∈B},y∈Zd為任意的.

下面證明

任取一k-sum-avoiding子集S?Er.若|S|>kd?1(2k?2)r,則必存在i(0≤i≤r?1),使得

且滿足

又因為當d≥3時,

故i

因此對任意的j=0,1,···,kd?1(2k?2),存在b0,b1,···,bkd?1(2k?2)∈Br?i,使得

由抽屜原理知存在一子集

其中|B′|>2k?2使得如下結論成立.對于任意的c1,c2∈B′和j∈{2,3,···,d},都有

其中c(i)表示向量c的第i個分量.因此由引理2.2知,存在k個向量bi1,bi2,···,bik∈B′滿足:

又因為

可得

由引理2.1知

故b∈Br?i?1.因此當j=1,2,···,k且ki(bij+y)∈S時,有

矛盾.

接著對|Er|進行估計.若對每個則顯然

這樣就有

下面作映射

顯然這個映射保持集合的基數和加法關系不變.設A1是映射?:ErBZ_74_1646_2840_1692_2886的像集.取y充分大,則像集A1的元素全為正整數,且

最后,取A1中最大的n個元素構成集合A.顯然A中任意k個不同元素之和不屬于A1A,故

[1] Choi S L G.On a combinatorial problem in number theory[J].Proc.London Math.Soc.,1971,23:629-641.

[2] Rusza I Z.Sum-avoiding subsets[J].Ramanujan J.,2005,9:77-82.

[3] Behrend F A.On sets of integers which contain no three terms in arithmetical progression[J].Proc.Nat. Acad.Sci.,1946,32:331-332.

[4] Sudakov B,Szemer′edi B and Vu V H.On a question of Erd¨os and Moser[J].Duke Math.,2005,129:129-155.

[5] 崔麗雯,楊勝良.廣義的k階Fibonacci-Jacobsthal序列[J].純粹數學與應用數學,2011,27(6):819-824.

[6] Erd¨os P,Ginzburg A,Ziv A.Theorem in the additive number theory[J].Bull.Research Council Israel., 1961,10F:41-43.

On the cardinality of k-sum-avoiding subsets

Zhao Qingqing
(Wentian College,Hohai University,Maanshan243031,China)

For a positive integer k,we call a subset S?A k-sum-avoiding,if any sum of k distinct elements taken from S does not belong to A.In this paper,we estimate the maximal cardinality of k-sum-avoiding subsets S of A when|A|=n.

sum-avoiding subsets,maximal cardinality,k-sum-avoiding subsets

O156.1

A

1008-5513(2014)05-0507-05

10.3969/j.issn.1008-5513.2014.05.012

2014-05-20.

趙青青(1985-),碩士,講師,研究方向：數論.

2010 MSC:11A10