دنباله‌های بیتی

**دنباله‌های بیتی**  یکی از مباحث موجود در *نظریه اعداد* و *ریاضیات گسسته* هستند که به دلیل ویژگی‌های منحصر به فردشان در تقسیم‌بندی اعداد حقیقی و کاربردهایشان در *الگوریتم‌ها* و *رمزنگاری* مورد توجه قرار گرفته‌اند. این دنباله‌ها با استفاده از یک عدد حقیقی مثبت r \geq 1 تعریف می‌شوند.

به این ترتیب، دنباله بیتی مربوط به r به صورت زیر بیان می‌شود:

A_r = \{ \lfloor nr \rfloor : n \in \mathbb{N} \}

به عنوان مثال، A_1 = \mathbb{N}، اما ویژگی کلیدی دنباله‌های بیتی در ارتباط آن‌ها با قضیه ریلی نهفته است که به موجب آن دو دنباله بیتی مکمل یکدیگر می‌شوند و تمام اعداد صحیح مثبت را بدون هم‌پوشانی پوشش می‌دهند.

## قضیه ریلی (Rayleigh theorem)
اگر \alpha, \beta > 1 دو عدد گنگ باشند که \frac{1}{\alpha} + \frac{1}{\beta} = 1 آنگاه دنباله‌های A_\alpha و A_\beta مجموعه اعداد طبیعی \mathbb{N} را افراز می‌کنند.

### اثبات قضیه
ابتدا برای عدد ۱ بررسی می‌کنیم:


1 \in A_\alpha \iff 1 = \lfloor \alpha \rfloor \iff 1 


1 \in A_\beta \iff 1 = \lfloor \beta \rfloor \iff 1 


\frac{1}{\alpha} + \frac{1}{\beta} = 1, \, (\alpha, \beta \neq 2) \implies \min(\alpha, \beta) 

پس ثابت شد عدد ۱ عضو دقیقاً یکی از دو مجموعه A_\alpha و A_\beta است.

حال کافی است ثابت کنیم برای هر m \in \mathbb{N}، مجموعه‌های A_\alpha \cap \{1, \cdots, m\} و A_\beta \cap \{1, \cdots, m\} مجموعه \{1, \cdots, m\}  را افراز می‌کنند.

برای این کار نیاز داریم تا اندازه مجموعه A_\alpha \cap \{1, \cdots, m\} را محاسبه کنیم.
بزرگ‌ترین n \in \mathbb{N} که \lfloor
n \alpha \rfloor عضو مجموعه بالا باشد را در نظر بگیرید. در این صورت خواهیم داشت:


n \alpha 


(n + 1) \alpha > m + 1


از دو عبارت بالا نتیجه می‌شود کهn = \left\lfloor \frac{m + 1}{\alpha} \right\rfloor و لذا \left\vert A_\alpha \cap \{1, \cdots, m\} \right\vert = \left\lfloor \frac{m + 1}{\alpha} \right\rfloor.

با توجه به گنگ بودن \alpha و \beta داریم:


\frac{m + 1}{\alpha} - 1 


\frac{m + 1}{\beta} - 1 

با جمع دو نامساوی بالا:


(m + 1) \left( \frac{1}{\alpha} + \frac{1}{\beta} \right) - 2 = m - 1 

عبارت وسط اکیداً بین دو عدد طبیعی متوالی قرار گرفته است پس:


\left\lfloor \frac{m + 1}{\alpha} \right\rfloor + \left\lfloor \frac{m + 1}{\beta} \right\rfloor = m


اکنون حکمی را که به دنبال اثبات آن بودیم را به کمک استقراء قوی ثابت می‌کنیم.
حالت پایه m = 1 را قبلاً بررسی کردیم.
فرض کنیم برای هر k  حکم برقرار باشد یعنی A_\alpha \cap \{1, \cdots, k\} و A_\beta \cap \{1, \cdots, k\} مجموعه \{1, \cdots, k\} را افراز کنند. داریم:


\left\vert (A_\alpha \cap \{1, \cdots, m + 1\}) \cup (A_\beta \cap \{1, \cdots, m + 1\}) \right\vert =
\left\lfloor \frac{m + 2}{\alpha} \right\rfloor +
\left\lfloor \frac{m + 2}{\beta} \right\rfloor - s = m + 1 - s


که s = \left\vert A_\alpha \cap A_\beta \cap \{1, \cdots, m + 1\} \right\vert.

با توجه به فرض s می‌تواند مقدار صفر یا یک را اختیار کند، اگر s = 0 حکم به‌سادگی نتیجه می‌شود.
اگر s = 1 یعنی m + 1 \in A_\alpha \cap A_\beta \cap \{1, \cdots, m + 1\} و یعنی:


\left\vert (A_\alpha \cap \{1, \cdots, m + 1\}) \cup (A_\beta \cap \{1, \cdots, m + 1\}) \right\vert = m + 1


ولی با جای‌گذاری مقدار s در رابطه‌ای که بالا به‌دست آوردیم داریم:


\left\vert (A_\alpha \cap \{1, \cdots, m + 1\}) \cup (A_\beta \cap \{1, \cdots, m + 1\}) \right\vert = m


که تناقض است پس s فقط می‌تواند مقدار صفر را اختیار کند و این اثبات حکم را به اتمام می‌رساند.
از آن‌جایی که حکم را برای تمامی mها ثابت کردیم قضیه ریلی به‌طور خودکار نتیجه می‌شود.

## خواص
چند خاصیت دنباله‌های بیتی:
# اگر k, l \in \mathbb{Q} آنگاه A_k \cap A_l = A_{[k, l]} \neq \varnothing.
# اگر \alpha گنگ و s گویا باشد آنگاه A_\alpha \cap A_s \neq \varnothing.
# هرگاه \alpha گنگ باشد:

A_\alpha^c = A_{\frac{\alpha}{\alpha - 1}}
.

۴) برای هر m صحیح و \beta \in \mathbb{Q}^c داریم A_{m\beta} \subseteq A_\beta.

در این لحظه می‌توان چند پرسش کلی طرح کرد!

- در چه صورت A_\alpha \cap A_\beta = \varnothing؟

- در چه صورت A_\alpha \cup A_\beta = \mathbb{N}؟

- آیا عکس خاصیت ۳ برقرار است؟

- آیا عکس خاصیت ۴ برقرار است؟

بررسی پرسش آخر:


A_\beta^c = A_{\frac{\beta}{\beta - 1}} \implies A_{\frac{m\beta}{\beta - 1}} \subseteq A_\beta^c \implies A_{\beta} \subseteq A_{\frac{m\beta}{\beta - 1}}^c = A_\gamma



\frac{\beta - 1}{m\beta} + \frac{1}{\gamma} = 1 \implies \gamma = \frac{m\beta}{(m - 1)\beta + 1}


پس:

A_\beta \subseteq A_{\frac{m\beta}{(m - 1)\beta + 1}}
.

قبل از بیان خاصیت آخر نیاز به تعریف چگالی است،
برای  A \subseteq \mathbb{N} ، چگالی به شکل زیر تعریف می‌شود:


\rho(A) = \lim_{n \to \infty} \frac{n}


می‌توان به رابطه \rho(A^C) = 1 - \rho(A) نیز اشاره کرد.
حال برای دنباله بیتی دل‌خواه داریم:

5)  \rho(A_\alpha) = \frac{1}{\alpha} 

## اثباتی دیگر برای قضیه ریلی
یکی از اثبات‌هایی که برای قضیه ریلی وجود دارد اثباتی است که از تابع جزء اعشاری (Fractional Part Function) و خواص آن کمک می‌گیرد.

برای هر عدد حقیقی  x  این تابع به این شکل تعریف می‌شود:
 f(x) = \{x\} = x - \lfloor x \rfloor 
* لم. اگر  x  و  y  دو عدد ناصحیح باشند بطوریکه جمع آن‌ها صحیح باشد آنگاه  f(x) + f(y) = 1 

اثبات. چون  x  و  y  صحیح نیستند پس وجود دارد
 0 
بطوریکه:

 f(x) = x - \lfloor x \rfloor = \epsilon 

 f(y) = y - \lfloor y \rfloor = \delta 

با جمع دو تساوی بالا خواهیم داشت:
 f(x) + f(y) = x + y - (\lfloor x \rfloor + \lfloor y \rfloor) = \epsilon + \delta 

از فرض نتیجه می‌شود، عبارت وسط تساوی عددی صحیح است لذا سمت راست نیز باید چنین باشد که تنها امکان این است که  \epsilon + \delta = 1 . بنابراین لم ثابت می‌شود.

قبلاً نشان دادیم که برای هر m طبیعی داریم:

|A_\alpha \cap \{1, \dots, m\}| = \lfloor \frac{m+1}{\alpha} \rfloor


حال توجه کنید که \frac{m+1}{\alpha} و \frac{m+1}{\beta} در شرایط لم صدق می‌کنند؛ لذا خواهیم داشت:

f\left(\frac{m+1}{\alpha}\right) + f\left(\frac{m+1}{\beta}\right) = 1 \implies \lfloor \frac{m+1}{\alpha} \rfloor + \lfloor \frac{m+1}{\beta} \rfloor = m


پس:
(A_\alpha \cap \{1, \dots, m\}) \cup (A_\beta \cap \{1, \dots, m\}) = \{1, \dots, m\}

با استفاده از این تابع می‌توان فهمید که اگر x \in A_\alpha باشد، آنگاه x باید در چه شرطی صدق کند:

x \in A_\alpha \implies \exists n \in \mathbb{N} \; \text{s.t.} \; x = \lfloor n \alpha \rfloor \implies \exists 0 

با استفاده از تابع جزء اعشاری داریم:

f\left(\frac{-x}{\alpha}\right) = \frac{\varepsilon}{\alpha} \implies f\left(\frac{-x}{\alpha}\right) 

مشابهاً برای A_\beta این شرط نتیجه می‌شود.

حال اگر z \in A_\alpha \cap A_\beta، طبق شرطی که به‌دست آوردیم:

f\left(\frac{-z}{\alpha}\right) 

توجه کنید که \frac{-z}{\alpha} و \frac{-z}{\beta} در شرایط لم صدق می‌کنند. پس با جمع کردن طرفین دو نابرابری خواهیم داشت:

f\left(\frac{-z}{\alpha}\right) + f\left(\frac{-z}{\beta}\right) = 1 

که تناقض است. پس:

A_\alpha \cap A_\beta = \emptyset


بنابراین A_\alpha و A_\beta مجموعه اعداد طبیعی را افراز می‌کنند.

## بازی ویتوف
بازی ویتوف (Wythoff's game) یک بازی دو نفره با قواعدی ساده و نتایجی شگفت‌انگیز است. این بازی که به افتخار ریاضی‌دان هلندی *ویلیم ویتوف* نام‌گذاری شده است، یکی از بهترین نمونه‌های ارتباط بین ریاضیات نظری و استراتژی در بازی‌ها است. 
در این بازی، دو دسته مهره وجود دارد. بازیکنان به نوبت بازی می‌کنند و در هر نوبت می‌توانند:
# از یکی از دسته‌ها هر تعداد دلخواه مهره بردارند.
# یا از هر دو دسته، تعداد برابری مهره بردارند.
هدف این است که تمام مهره‌ها از بازی خارج شوند، بازیکنی که این کار را انجام دهد برنده است

توصیفی معادل از بازی بعدها توسط ریاضی‌دان *Rufus Isaacs* معرفی شد که بازی روی یک صفحه شطرنجی انجام می‌شود، به این صورت که در ابتدا وزیر یا یک مهره روی صفحه قرار داده شده است حال بازیکنان به نوبت می‌توانند مهره یا وزیر را حرکت دهند که قوانین خودش را دارد:
بی‌قاب|راست
۱. به تعداد دلخواه خانه می‌توان به سمت چپ رفت

۲. به تعداد دلخواه خانه می‌توان به سمت پایین رفت

۳. یا به تعداد دلخواه به صورت قطری حرکت کند
برنده کسی است که بتواند مهره را به خانه گوشه چپ پایین ببرد

برای معادل ساری کافیست روی این صفحه محورهای مختصات را سوار کنیم بطوریکه خانه برنده مختصاتی برابر (0,0) داشته باشد. حال مختصات اولیه وزیر که (x,y) است نشانگر تعداد دسته مهره‌های ما در صورت قبلی بازی است که به‌ترتیب به تعداد x و y مهره دارند

### استراتژی بهینه
برای توضیح استراتژی با مدل دوم بازی کار می‌کنیم.
همان‌طور که گفته شد هر موقعیت در این بازی را می‌توان با یک زوج مرتب صحیح (x,y) که در آن x\leq y است توصیف کرد که این جفت اعداد اندازه هر دو دسته مهره در موقعیت فعلی یا مختصات وزیر را نشان می‌دهد. استراتژی بازی حول دو نوع موقعیت می‌چرخد: **موقعیت سرد** و **موقعیت گرم**. در یک موقعیت سرد، بازیکنی که نوبت حرکتش است، در صورت بازی بهینه بازنده خواهد بود، در حالی که در یک موقعیت گرم، بازیکنی که نوبت حرکتش است، در صورت بازی بهینه برنده می‌شود. استراتژی بهینه در یک موقعیت گرم این است که وزیر را به هر موقعیت سردی که قابل دسترسی است، منتقل کند.

طبقه‌بندی موقعیت‌ها به دو دسته سرد و گرم به صورت بازگشتی و با استفاده از سه قانون زیر انجام می‌شود:
* ۱. موقعیت (0,0) یک **موقعیت سرد** است.
* ۲. هر موقعیتی که بتوان با یک حرکت از آن به یک موقعیت سرد رسید، یک **موقعیت گرم** است.
* ۳. اگر هر حرکتی از یک موقعیت به یک موقعیت گرم منتهی شود، آن موقعیت **سرد** است.
برای مثال در یک صفحه 9*9 خانه‌های **سرد** و **گرم** به این صورت هستند:بی‌قاب|وسط|250px

ویتوف کشف کرد که موقعیت‌های سرد یک الگوی منظم را دنبال می‌کنند که با نسبت طلایی تعیین می‌شود. به‌طور مشخص، اگر n یک عدد طبیعی باشد، آنگاه:


x_n = \lfloor n \phi \rfloor = \lfloor y_n \phi \rfloor - y_n



y_n = \lfloor n \phi^2 \rfloor = \lceil x_n \phi \rceil = x_n + n


که در اینجا \phi نسبت طلایی است در این حالت، (x_n,y_n) و (y_n,x_n) دو موقعیت سرد n-ام هستند.

همچنین برای هر n داریم: y_n-x_n=n

این دو دنباله x_n و y_n دنباله‌های بیتی مرتبط با معادله زیر هستند:


\frac{1}{\phi} + \frac{1}{\phi^2} = 1


- x_n: این دنباله موقعیت‌های سرد کوچک‌تر را توصیف می‌کند:

1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... 

- y_n: این دنباله موقعیت‌های سرد بزرگ‌تر را توصیف می‌کند.

2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... 

همان‌طور که در همه دنباله‌های بیتی صادق است، این دو دنباله مکمل هستند؛ یعنی اگر یک عدد طبیعی در یکی از دنباله‌ها ظاهر شود، در دنباله دیگر ظاهر نخواهد شد. این ویژگی برای بازی ویتوف و استراتژی‌های آن بسیار مهم است، زیرا به تفکیک کامل موقعیت‌ها کمک می‌کند و نقش مهمی در تعیین حرکات برنده دارد.

## کاربرد در رمزنگاری
### شرح کاربرد
دنباله‌های بیتی به دلیل خواص منحصر به فردشان، در رمزنگاری کاربردهای جالبی دارند. این دنباله‌ها دو ویژگی اساسی دارند که آن‌ها را برای کاربردهای رمزنگاری مناسب می‌کند:
* رمزنگاری پیام‌ها:
موقعیت‌های خاص در دنباله‌های بیتی می‌توانند به کدگذاری اطلاعات کمک کنند. برای نمونه، می‌توان حروف یا کلمات یک پیام را به مقادیر متناظر در دنباله‌های بیتی نگاشت کرد.
* ایجاد الگوریتم‌های امن:
الگوریتم‌های رمزنگاری مبتنی بر خواص ریاضی دنباله‌های بیتی، به دلیل ساختار منظم اما غیرقابل پیش‌بینی، در برابر حملات مقاومت بالایی دارند.

### مثال عملی
#### گام‌های رمزنگاری
* **۱ - تولید کلید**
برای تولید دنباله بیتی از عدد گنگ r=\sqrt{2}\pi استفاده می‌کنیم؛ لذا فرمول تولید کلید برای هر k طبیعی برابراست با: C_k=\left\lfloor k\sqrt{2}\pi \right\rfloor.

برای k=1,2,3,... کلید تولید شده عبارت است از:

(4,8,13,17,22,26,31,35,39,44,48,53,57,62,66,71,75,79,...)

این بردار را تا طول پیام ادامه می‌دهیم.
* **۲ - تبدیل متن به کد**
پیام:
 To: Logistics Command, Shipment of ammunition and medical supplies delayed by 12 hours. Adjust plans accordingly. Expect new delivery at 1800 hours. Heil Hitler

حال به حروف A تا Z اعداد ۰ تا ۲۵ را نسبت می‌دهیم اگر در متن، عدد وجود داشت آن را هم به صورت متن می‌نویسیم مثلاً در پیام بالا عدد ۱۲ وجود دارد، جای آن را با کلمه twelve عوض می‌کنیم.
بدون در نطر گرفتن علائم نگارشی پیام تبدیل به بردار زیر می‌شود:
 **P**=[۱۹٬۱۴٬۱۱٬۱۴٬۶٬۸,...]
* **۳ - اعمال شیفت**
برای به‌دست آوردن بردار رمز شده یعنی D، به این صورت عمل می‌کنیم: D_k \equiv P_k + C_k \pmod{26} 

لذا D می‌شود:
 D=[۲۳ ۱۰ ۰ ۲۱ ۶ ۰ ۳ ۲۲ ۳ ۱۶ ۲۴ ۱ ۵ ۲۲ ۱۴ ۲۰ ۰ ۸ ۱۶ ۲۳ ۱۷ ۱۶ ۵ ۱۶ ۱۷ ۱۶ ۳ ۱۳ ۰ ۴ ۲۳ ۲۳ ۹ ۲۲ ۰ ۷ ۵ ۲۳ ۲ ۸ ۱۶ ۱۸ ۲ ۱۹ ۱۷ ۳ ۲۰ ۲۳ ۲۳ ۱۷ ۴ ۲۳ ۱۱ ۱ ۱۵ ۲۲ ۲۵ ۱۸ ۱۸ ۲۵ ۱۶ ۱۴ ۶ ۲۲ ۱۱ ۲۵ ۲۰ ۲۱ ۲۰ ۲۳ ۲۴ ۱۹ ۱۹ ۱۷ ۷ ۰ ۱ ۲۲ ۲۰ ۲۴ ۱۴ ۸ ۲۲ ۱۱ ۱۸ ۲۳ ۲۱ ۲۱ ۱۶ ۸ ۱۳ ۸ ۱۲ ۱۰ ۷ ۱۹ ۱۶ ۲۲ ۲۰ ۵ ۱۶ ۲۳ ۱۴ ۲۳ ۱۰ ۱۹ ۳ ۳ ۲۲ ۲۲ ۱۱ ۱۷ ۱۸ ۲۳ ۲۳ ۱۷ ۳ ۱۶ ۸ ۱۷ ۲۴ ۵ ۴ ۳ ۱۹ ۲۰ ۲۵ ۷ ۱ ۲۳ ۱۴ ۷ ۱۲ ۱۸ ۲۳ ۹ ۱۷ ۲۴ ۳ ۲۱ ۱۷ ۱۶ ۱۵ ۴ ۲۴ ۵ ۲۱ ۱۷ ۱۲ ۱ ۲۰ ۲۴ ۸ ۲۰ ۲۵]
* **۴ - متن رمزنگاری‌شده**
پس از اعمال شیفت، بردار D را به حروف برمی‌گردانیم و متن رمز شده را ۵ تا ۵ برش می‌زنیم، خواهیم داشت:
 XKAVG ADWDQ YBFWO UAIQX RQFQR QDNAE XXJWA HFXCI QSCTR DUXXR EXLBP WZSSZ QOGWL ZUVUX YTTRH ABWUY OIWLS XVVQI NIMKH TQWUF QXOXK TDDWW LRSXX RDQIR YFEDT UZHBX OHMSX JRYDV RQPEY FVRMB UYIUZ

#### رمزگشایی
برای رمزگشایی، همان عملیات شیفت را خلاف اعمال می‌کنیم یعنی برای به‌دست آوردن متن اصلی P داریم: P_k \equiv D_k - C_k \pmod{26} 

متن اصلی بدون تغییر بازیابی می‌شود.

## تاریخچه
دنباله‌های بیتی (Beatty sequences) نام خود را از مسئله‌ای گرفته‌اند که در سال ۱۹۲۶ توسط ساموئل بیتی در مجله The American Mathematical Monthly مطرح شد. این مسئله احتمالاً یکی از پرارجاع‌ترین مسائلی است که تاکنون در این مجله مطرح شده است. با این حال، حتی پیش از آن، در سال ۱۸۹۴، چنین دنباله‌هایی به‌طور مختصر توسط لرد ریلی (Lord Rayleigh) در ویرایش دوم کتاب The Theory of Sound ذکر شده بودند.

## مطالعه بیش‌تر
چند منبع مرتبط با این دنباله‌ها معرفی می‌شود:
* مقاله:Beatty Sequences for a Quadratic Irrational: Decidability and Applications":
این مقاله در arXiv موجود است و به بررسی دنباله‌های بیتی برای اعداد گنگ درجه دوم می‌پردازد.
* مقاله:Beatty sequences and Wythoff sequences, generalized": این مقاله در The Fibonacci Quarterly منتشر شده و به تعمیم دنباله‌های بیتی و ویتوف می‌پردازد.
* مقاله:Beatty sequences and multiplicative number theory": این مقاله به ارتباط بین دنباله‌های بیتی و نظریه اعداد ضربی می‌پردازد.
* مقاله:Beatty Sequences, Fibonacci numbers, and the golden ratio": این مقاله به بررسی ارتباط بین دنباله‌های بیتی، اعداد فیبوناچی و نسبت طلایی می‌پردازد.
* صفحه ویکی‌پدیا دربارهٔ دنباله بیتی