Finite Playground

To verify is human; to prove, divine.

Zero-sum subsets

Leave a comment

這個有趣的(小)問題是在 MathOverflow 上看到的。

假設我們有一個有限集合S=\{a_1, \ldots, a_n\}為某個群 (如自然數) 的子集, 滿足底下條件:

任何S中的元素都可以寫成另外兩個S中元素的和;也就是說令S+S = \{a_i+a_j \mid a_i,a_j \in S\},則S \subseteq S+S

試證明:S中存在一個非空子集Z使得Z中所有元素相加為零。

我們稱這樣的子集Z零和子集 (zero-sum subset)。

零和字集在加性組合學 (additive combinatorics) 中是個被廣泛研究的主題;例如在一個群G當中,若任意給定d個元素形成的集合其中都有零和子集,滿足這樣條件最小的d,我們稱作 restricted Davenport number\hat D(G)。在 Szemeredi 的 “On a conjecture of Erdos and Heilbronn” 中,他證明了

\hat D(G) = O(\sqrt{n}),

其中nG的大小。

但是由所謂 sum-full (也就是S \subseteq S+S) 這樣的條件而保證零和子集的存在性,在文獻中卻是沒有看過… 似乎是個很有趣的問題!目前為止只能想到一些標準化為圖論問題的方法,反證了幾個過於樂觀的猜想,卻沒有進一步的結果… 也許需要一些其他的工具來證明。有沒有什麼想法呢?

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s