تسلسل الإشارات

الموسوعة الحرة

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

تُدرس هذه المتتاليات عادةً في نظرية التباين .

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

في حوالي عام 1932، افترض عالم الرياضيات بول إيردوس أنه بالنسبة لأي متتالية لانهائية من ±1(x1،x2،...){\displaystyle (x_{1},x_{2},\ldots )}وأي عدد صحيح C ، يوجد عددان صحيحان k و d بحيث

|∑أنا=1كxأنا⋅د|>ج.{\displaystyle \left|\sum _{i=1}^{k}x_{i\cdot d}\right|>C.}

تطلب مسألة التناقض في إردوش إثبات أو دحض هذه الفرضية.

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

في سبتمبر 2015، أعلن تيرينس تاو عن برهانٍ للفرضية، مستندًا إلى عملٍ أُنجز عام 2010 خلال مؤتمر Polymath5 (وهو شكلٌ من أشكال التعهيد الجماعي المُطبَّق على الرياضيات) واقتراحٍ قدّمه عالم الرياضيات الألماني أوفه ستروينسكي على مدونة تاو. [ 3 ] [ 4 ] نُشر برهانه عام 2016، كأول ورقة بحثية في مجلة التحليل المنفصل الجديدة . [ 5 ]

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

رموز باركر

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

xج ل ج=1،...،شمال،{\displaystyle x_{j}{\text{ for }}j=1,\ldots ,N,}

بحيث

|∑ج=1شمال-vxجxج+v|≤1{\displaystyle \left|\sum _{j=1}^{Nv}x_{j}x_{j+v}\right|\leq 1}

للجميع1≤v<شمال{\displaystyle 1\leq v<N}.[7]

Barker codes of lengths 11 and 13 are used in direct-sequence spread spectrum and pulse compression radar systems because of their low autocorrelation properties.

See also

Notes

  1. ↑Konev, Boris; Lisitsa, Alexei (2014). "A SAT attack on the Erdős discrepancy conjecture". In Sinz, Carsten; Egly, Uwe (eds.). 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. Vol. 8561. Springer. pp. 219–226. arXiv:1402.2184. doi:10.1007/978-3-319-09284-3_17. ISBN 978-3-319-09283-6.
  2. ↑Aron, Jacob (February 17, 2014). "Wikipedia-size maths proof too big for humans to check". New Scientist. Retrieved February 18, 2014.
  3. ↑"Famous math problem solved thanks to crowdsourcing". USA Today. September 28, 2015.
  4. ↑Aron, Jacob (30 September 2015). "Crowds beat computers in answer to Wikipedia-sized maths problem". New Scientist. Retrieved October 21, 2015.
  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. ↑Li, Wentian; Thanos, Dimitrios; Provata, Astero (2019-01-14). "Quantifying local randomness in human DNA and RNA sequences using Erdös motifs". Journal of Theoretical Biology. 461: 41–50. arXiv:1805.10248. Bibcode:2019JThBi.461...41L. doi:10.1016/j.jtbi.2018.09.031. ISSN 0022-5193. PMID 30336158. S2CID 52901027.
  7. ↑Barker, R. H. (1953). "Group Synchronizing of Binary Digital Sequences". Communication Theory. London: Butterworth. pp. 273–287.

References