در تئوری اعداد افزودنی و ترکیبی ، یک جمع محدود دارای شکل است

S = \ {a_ {1} + \ cdots + a_ {n}: \ a_ {1} \ in A_ {1}، \ ldots، a_ {n} \ in A_ {n} \ {\ mathrm {and}} \ P (a_ {1} ، \ ldots ، a_ {n}) \ not = 0 \} ،

جایی که A_ {1} ، \ ldot ، A_ {n}زیر مجموعه ناتهی محدود یک هستند درست F وP (x_ {1} ، \ ldots ، x_ {n})چند جمله ای بیش از F است .

اگرپ به عنوان مثال یک تابع غیر صفر ثابت است P (x_ {1} ، \ ldots ، x_ {n}) = 1 برای هرچی x_ {1} ، \ ldot ، x_ {n}، و سپس S که معمول است بهA_ {1} + \ cdots + A_ {n}که اگر با nA نشان داده شودA_ {1} = \ cdots = A_ {n} = A.

چه زمانی

P (x_ {1} ، \ ldots ، x_ {n}) = \ prod _ {{1 \ leq i <j \ leq n}} (x_ {j} -x_ {i}) ،

S به صورت نوشته شده استA_ {1} \ dotplus \ cdots \ dotplus A_ {n} که با نشان داده می شود n ^ {{\ wedge}} الف اگر A_ {1} = \ cdots = A_ {n} = A.

توجه داشته باشید که | S | > 0 اگر و فقط در صورت وجودa_ {1} \ در A_ {1} ، \ ldot ، a_ {n} \ در A_ {n} با P (a_ {1} ، \ ldots ، a_ {n}) \ not = 0.

 

فهرست

قضیه کوشی – داونپورت [ ویرایش ]

قضیه کوشی-داونپورت به نام بعد از آگوستین لوییز کوشی و هارولد داونپورت ادعا میکند که هر نخست ص و زیر مجموعه های غیر خالی و B از نخست سفارش گروه دوری {\ mathbb {Z}} / p {\ mathbb {Z}}ما نابرابری داریم [1] [2] [3]

{\ displaystyle | A + B | \ geq \ min \ {p، \ | A | + | B | -1 \}}

جایی که {\ displaystyle A + B: = \ {a + b {\ pmod {p}} | a \ in A ، b \ in B \}}، یعنی ما از حساب مدولار استفاده می کنیم .

ما ممکن است از این برای استنباط قضیه Erdős – Ginzburg – Ziv استفاده کنیم : با توجه به توالی عناصر 2 n -1 در گروه چرخه\ mathbb {Z} / n \ mathbb {Z} ، n عنصری وجود دارد که جمع می شوند به modulo n صفر . (در اینجا n نیازی به درجه اول بودن ندارد.) [4] [5]

یک نتیجه مستقیم از معادلات کوشی-داونپورت قضیه: با توجه به هر رشته S از ص -1 یا عناصر غیر صفر بیشتر، نه لزوما متمایز، از{\ mathbb {Z}} / p {\ mathbb {Z}}، هر عنصر از {\ mathbb {Z}} / p {\ mathbb {Z}}می تواند به عنوان مجموع عناصر برخی از دنباله ها (احتمالاً خالی) از S نوشته شود . [6]

قضیه Kneser این موضوع را به گروههای عمومی abelian تعمیم می دهد. [7]

حدس Erdős – Heilbronn [ ویرایش ]

حدس اردوش-هایلبرون توسط مطرح پل Erdős و هانس هایلبرون در سال 1964 کشورهایی که| 2 ^ {\ wedge} A | \ geq \ min \ {p، 2 | A | -3 \}اگر p یک درجه اول است و A یک زیرمجموعه خالی از فیلد Z / p Z است . [8] این اولین بار توسط JA Dias da Silva و YO Hamidoune در سال 1994 تأیید شد [9] که نشان دادند

| n ^ {\ wedge} A | \ geq \ min \ {p (F)، \ n | A | -n ^ {2} +1 \}،

که در آن زیر مجموعه غیر خالی محدود از یک میدان است F و P ( F ) اول است ص اگر F است از مشخصه ص ، و ص ( F ) = ∞ اگر F است از مشخصه 0. پسوند های مختلف از این نتیجه را از داده شد Noga Alon ، MB Nathanson و I. Ruzsa در 1996 ، [10] QH Hou و Zhi-Wei Sun در 2002 ، [11] و G. Karolyi در 2004. [12]

Nullstellensatz ترکیبی [ ویرایش ]

یک ابزار قدرتمند در مطالعه مرزهای پایین تر برای کارایی های مختلف از مجموعه های مختلف محدود شده ، اصل اساسی زیر است: Nullstellensatz ترکیبی . [13] بگذاریدf (x_ {1} ، \ ldots ، x_ {n})چند جمله ای بیش از یک قسمت F باشد. فرض کنید ضریب یک جمله ایx_ {1} ^ {{k_ {1}}} \ cdots x_ {n} ^ {{k_ {n}}} که درf (x_ {1} ، \ ldots ، x_ {n}) غیر صفر است و k_ {1} + \ cdots + k_ {n}است درجه کل ازf (x_ {1} ، \ ldots ، x_ {n}). اگرA_ {1} ، \ ldot ، A_ {n}زیرمجموعه های محدود F با| A_ {i} |> k_ {i} برای من = 1 ، \ ldots ، n، وجود داردa_ {1} \ در A_ {1} ، \ ldot ، a_ {n} \ در A_ {n} به طوری که f (a_ {1} ، \ ldots ، a_ {n}) \ not = 0.

به روش استفاده از Nullstellensatz ترکیبی روش چند جمله ای نیز گفته می شود. این ابزار در مقاله ای از N. Alon و M. Tarsi در سال 1989 ریشه دوانده است [14] و توسط Alon ، Nathanson و Ruzsa در 1995-1996 تولید شده است [10] و توسط Alon در سال 1999 اصلاح شده است. [13]

همچنین به [ ویرایش ] مراجعه کنید

منابع 

https://en.wikipedia.org/wiki/Restricted_sumset#Combinatorial_Nullstellensatz