متتالية الإشارة

متتالية الإشارة ، أو متتالية ±1 أو المتتالية ثنائي القطب في الرياضيات هي متتالية من الأعداد، كل منها إما 1 أو -1. أحد الأمثلة على ذلك هو التسلسل (1 ، −1 ، 1 ، −1 ،. . . ). تدرس هذه المتسلسلات بكثرة في نظرية التناقض .

مشكلة تناقض إيردوش

خمن الرياضي المجري بول إيردوش قرابة عام 1932 أنّه لأي متوالية لانهائية ±1 $(x_{1}, x_{2}, \dots)$ وأي عدد صحيح C، هناك أعداد صحيحة k و d تحقق ما يلي

$| \sum_{i = 1}^{k} x_{i \cdot d} | > C .$

لذلك تتطلب مشكلة تناقض إيردوش مبرهنة أو نقضاً لهذا التخمين.

أظهر أليكسي ليستسا و بوريس كونيف من جامعة ليفربول في فبراير 2014 ، أظهر أليكسي ليسيتسا وبوريس كونيف من جامعة ليفربول أن كل تسلسل مكون من 1161 عنصرًا أو أكثر يلبي التخمين في الحالة الخاصة C = 2 ، مما يثبت التخمين لـ C ≤ 2.^[1] وهو أفضل المتاح في ذلك الوقت. اعتمد إثباتهم على خوارزمية حاسوبية لحل SAT والتي يستهلك إخراجها 13 غيغابايت من البيانات، أي أكثر من نَص أرابيكا بأكمله في ذلك الوقت، لذلك لا يمكن التحقق منه بشكل مستقل من قبل علماء الرياضيات دون استخدام الآلة أو الحاسوب مرة أخرى. ^[2]

أعلن الرياضي الأسترالي تيرنس تاو عن إثبات لهذا التخمين، مبنياً على المشروع المنجز عام 2010 من خلال مشروع البوليماث (شكل من مصدر جماهيري المطبق في الرياضيات) واقتراح قدمه عالم الرياضيات الألماني أوي ستروينسكي في مدونة تاو.^[3]^[4] نشر إثباته عام 2016 ليكون أول مرقة بحثية في المجلة الجديدة (بالإنجليزية: Discrete Analysis)‏^[5]

اقترح تناقض إيردوش للمتسلسلات المحدودة مقياساً للعشوائية المحلية في تسلسل حمض نووي ريبوزي منقوص الأكسجين. يعتمد على حقيقة في المتواليات محددة الطول، يكون التناقض محدوداً. لدلك ستكون تلك المتسلسلات هي التي "تتجنب" أجزاء دورية محددة. من خلال مقارنة التوزيع المتوقع مقابل التوزيع المرصود في الحمض النووي أو استخدام مقاييس الارتباط الأخرى ، يمكن للمرء أن يستخلص استنتاجات تتعلق بالسلوك المحلي لتسلسل الحمض النووي.

رموز باركر

كود باركر هو سلسلة من قيم N من +1 و − 1 ،

x_{j} for j = 1, \dots, N

مثل :

| \sum_{j = 1}^{N - v} x_{j} x_{j + v} | \leq 1

لجميع $1 \leq v < N$ . ^[6]

تُستخدم شفرات باركر ذات الأطوال 11 و 13 في أنظمة رادار الطيف المنتشر ذات التسلسل المباشر وأنظمة رادار ضغط النبض بسبب خصائص الارتباط التلقائي المنخفضة.

انظر أيضا

المراجع

^ Konev، Boris؛ Lisitsa، Alexei (2014). "A SAT attack on the Erdős discrepancy conjecture". في Sinz، Carsten؛ Egly، Uwe (المحررون). Theory and Applications of Satisfiability Testing – SAT 2014 – 17th International Conference, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14–17, 2014, Proceedings. Lecture Notes in Computer Science. Springer. ج. 8561. ص. 219–226. arXiv:1402.2184. DOI:10.1007/978-3-319-09284-3_17.
^ Aron، Jacob (17 فبراير 2014). "Wikipedia-size maths proof too big for humans to check". نيو ساينتست. مؤرشف من الأصل في 2023-02-06. اطلع عليه بتاريخ 2014-02-18.
^ Famous math problem solved thanks to crowdsourcing. يو إس إيه توداي Sept. 28, 2015 نسخة محفوظة 2022-12-25 على موقع واي باك مشين.
^ Jacob Aron, Crowds beat computers in answer to Wikipedia-sized maths problem, نيو ساينتست, 30 Sep 15, retrieved 21.10.2015 نسخة محفوظة 2022-12-09 على موقع واي باك مشين.
^ Tao، Terence (2016). "The Erdős discrepancy problem". Discrete Analysis: 1–29. arXiv:1509.05363. DOI:10.19086/da.609. ISSN:2397-3129. MR:3533300. S2CID:59361755.
^ Barker, R. H. (1953). "Group Synchronizing of Binary Digital Sequences". Communication Theory. London: Butterworth. ص. 273–287.

مراجع

Chazelle، Bernard (24 يوليو 2000). The Discrepancy Method: Randomness and Complexity. Cambridge University Press. ISBN:0-521-77093-9. مؤرشف من الأصل في 2022-04-07.

روابط خارجية

مشكلة التناقض في Erd – مشروع Polymath
الكمبيوتر يكسر لغز Erdős - لكن لا يوجد عقل بشري يمكنه التحقق من الإجابة - المستقل (الجمعة ، 21 فبراير 2014)

[1] Konev، Boris؛ Lisitsa، Alexei (2014). "A SAT attack on the Erdős discrepancy conjecture". في Sinz، Carsten؛ Egly، Uwe (المحررون). Theory and Applications of Satisfiability Testing – SAT 2014 – 17th International Conference, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14–17, 2014, Proceedings. Lecture Notes in Computer Science. Springer. ج. 8561. ص. 219–226. arXiv:1402.2184. DOI:10.1007/978-3-319-09284-3_17.

[2] Aron، Jacob (17 فبراير 2014). "Wikipedia-size maths proof too big for humans to check". نيو ساينتست. مؤرشف من الأصل في 2023-02-06. اطلع عليه بتاريخ 2014-02-18.

[3] Famous math problem solved thanks to crowdsourcing. يو إس إيه توداي Sept. 28, 2015 نسخة محفوظة 2022-12-25 على موقع واي باك مشين.

[4] Jacob Aron, Crowds beat computers in answer to Wikipedia-sized maths problem, نيو ساينتست, 30 Sep 15, retrieved 21.10.2015 نسخة محفوظة 2022-12-09 على موقع واي باك مشين.

[5] Tao، Terence (2016). "The Erdős discrepancy problem". Discrete Analysis: 1–29. arXiv:1509.05363. DOI:10.19086/da.609. ISSN:2397-3129. MR:3533300. S2CID:59361755.

[6] Barker, R. H. (1953). "Group Synchronizing of Binary Digital Sequences". Communication Theory. London: Butterworth. ص. 273–287.

[1]

[2]

[3]

[4]

[5]

[6]