Consider the following self-map of the projective line over integers \(\mathbb{P}(\mathbb{Z})\): \[ T(a:b) = \left(\frac{a}{ord_2(a)}:\frac{3b+a}{ord_2(3b+a)}\right) \] where \(ord_2(a)\) is the largest power of \(2\) that divides \(a\). The question is the following:
If we define \(x_{n+1} = T(x_n)\) for an initial point \(x_0 = (a_0:b_0)\) do we always get a cycle. That is, for every inital point \((a_0:b_0)\) is there a \(k\>0\) and \(N\>0\) such that \(x_{N+k} = x_N\)?
Let us start with the order function. Rather, let me implement a function that returns a number divided by the \(p\)-part of that number
(defun reduction (n p)
(if (zerop (mod n p))
(reduction (/ n p) p)
n))REDUCTIONand let us test
(mapcar (lambda (m) (list m (reduction m 2))) (loop repeat 30 collect (1+ (random 1000))))((352 11) (17 17) (744 93) (741 741) (858 429) (763 763) (162 81) (274 137)
(180 45) (312 39) (171 171) (595 595) (25 25) (602 301) (605 605) (828 207)
(477 477) (398 199) (50 25) (379 379) (175 175) (8 1) (362 181) (174 87)
(940 235) (393 393) (845 845) (187 187) (656 41) (897 897))Next, I need a projective reduction:
(defun projective (xs)
(let* ((a (car xs))
(b (cadr xs))
(r (gcd a b)))
(list (/ a r) (/ b r))))PROJECTIVEand we test
(loop repeat 20 collect
(let ((xs (list (+ 2 (random 20)) (+ 2 (random 20)))))
(list xs (projective xs))))(((7 14) (1 2)) ((15 8) (15 8)) ((8 4) (2 1)) ((15 16) (15 16)) ((16 20) (4 5))
((13 20) (13 20)) ((9 4) (9 4)) ((18 18) (1 1)) ((4 6) (2 3)) ((6 11) (6 11))
((11 3) (11 3)) ((9 21) (3 7)) ((16 3) (16 3)) ((10 10) (1 1)) ((8 5) (8 5))
((13 14) (13 14)) ((20 11) (20 11)) ((16 10) (8 5)) ((13 12) (13 12))
((21 9) (7 3)))Let us implement the iteration function
(defun iterate (fn init &optional result)
(if (member init result :test #'equal)
(nreverse result)
(iterate fn (funcall fn init) (cons init result))))ITERATELet us test
(iterate (lambda (n) (mod (incf n) 10)) 0)(0 1 2 3 4 5 6 7 8 9)And finally the function that I would like to test:
(defun my-func (xs)
(let* ((a (car xs))
(b (cadr xs)))
(projective (list (reduction a 2) (reduction (+ a (* 3 b)) 2)))))MY-FUNCand let us test
(loop repeat 10 collect
(let ((a (1+ (random 100)))
(b (1+ (random 100))))
(iterate #'my-func (list a b))))(((90 18) (5 1))
((43 55) (43 13) (43 41) (43 83) (43 73) (43 131) (43 109) (43 185) (43 299)
(43 235) (43 187) (43 151) (43 31) (43 17) (43 47) (43 23) (43 7) (43 1))
((40 17) (5 91) (5 139) (5 211) (5 319) (5 481) (5 181) (5 137) (5 13) (5 11)
(5 19) (5 31) (5 49))
((70 52) (35 113) (35 187) (35 149) (35 241) (35 379) (35 293) (35 457)
(35 703) (35 67) (35 59) (35 53) (35 97) (35 163) (35 131) (35 107) (35 89)
(35 151) (35 61) (35 109) (35 181) (35 289) (35 451) (35 347) (35 269)
(35 421) (35 649) (35 991) (35 47) (35 11) (35 17) (35 43) (35 41) (35 79))
((81 87) (9 19) (3 11) (1 3) (1 5) (1 1)) ((34 85) (1 17) (1 13) (1 5) (1 1))
((9 68) (3 71) (1 9) (1 7) (1 11) (1 17) (1 13) (1 5) (1 1))
((83 63) (83 17) (83 67) (83 71) (83 37) (83 97) (83 187) (83 161) (83 283)
(83 233) (83 391) (83 157) (83 277) (83 457) (83 727))
((100 70) (5 31) (5 49) (5 19)) ((36 36) (1 1)))But we must check if the sequence terminates for all initial choice of points. Since we can’t do that, we are going to check if this is true for random initial points
(loop repeat 2000 collect
(let ((a (1+ (random 10000)))
(b (1+ (random 10000))))
(length (iterate #'my-func (list a b)))))(81 79 128 58 77 13 332 158 51 202 233 103 84 648 20 376 334 39 292 48 13 72 51
106 75 46 37 131 60 284 209 442 223 27 91 33 32 52 78 47 487 194 75 24 123 91
29 346 13 184 125 117 206 59 168 84 45 57 143 16 177 114 45 4 313 51 368 188
401 489 153 395 772 48 77 178 92 277 379 183 101 50 20 192 159 26 52 29 103 37
94 12 47 147 138 92 27 94 8 5 39 40 53 49 106 62 424 167 36 234 182 23 195 13
61 207 110 7 57 240 162 339 132 19 22 226 139 29 37 268 176 37 150 148 101 553
64 29 111 194 256 8 52 188 61 51 258 89 50 42 59 81 29 294 102 125 21 8 65 210
340 183 180 129 135 187 43 168 56 29 43 106 110 36 82 50 72 62 413 70 177 187
8 294 203 93 35 498 183 85 277 36 72 20 321 283 36 214 26 36 57 141 230 18 143
6 48 118 113 35 135 11 34 147 236 209 244 150 83 32 193 179 187 132 125 452 25
79 14 43 231 143 421 61 32 230 33 121 69 84 254 41 87 229 523 185 42 102 330
69 221 77 55 57 238 19 249 72 34 36 82 96 149 590 141 55 106 42 33 423 324 411
114 398 56 101 5 30 86 10 177 55 159 319 32 142 372 271 53 61 48 117 27 193
170 37 144 80 87 114 95 60 143 317 49 142 299 159 160 50 20 238 70 155 221 61
75 33 230 82 17 72 25 260 91 85 48 32 28 133 350 233 233 375 117 42 78 17 82
86 68 65 89 39 588 27 69 78 141 50 72 325 10 41 85 16 49 40 478 281 91 472 95
24 28 6 244 22 59 39 70 55 51 44 139 59 66 87 125 16 287 595 35 815 415 182
273 50 16 293 54 30 167 377 172 167 240 95 226 19 195 101 72 186 136 315 57 54
73 766 18 45 7 28 291 290 377 56 116 90 14 145 261 165 41 92 145 31 152 13 93
141 90 220 36 35 88 271 301 89 142 84 49 525 43 139 17 85 280 125 254 71 414
211 94 161 194 508 40 140 98 190 91 171 276 15 119 136 10 29 177 699 38 281
172 37 69 93 267 9 146 135 4 32 473 34 250 4 450 97 106 73 80 438 66 77 245
153 28 39 114 30 84 49 64 101 71 110 23 16 21 35 413 235 600 278 58 51 85 373
55 76 11 64 71 59 164 165 273 85 19 37 124 216 22 365 73 471 15 57 53 42 291
272 36 61 386 116 630 320 12 14 65 184 118 26 26 319 170 50 63 330 161 105 159
65 23 113 374 10 219 356 182 312 92 80 69 79 172 38 221 188 92 44 96 196 211
44 207 70 179 20 60 55 82 213 27 304 45 164 117 58 627 120 66 100 23 139 62 31
87 331 197 24 131 39 20 108 221 76 52 287 306 471 57 59 326 56 62 213 176 270
136 171 19 104 84 43 23 369 300 265 574 50 28 355 196 314 32 193 27 241 39 82
31 23 161 265 15 90 346 263 197 71 213 265 369 242 384 112 6 38 127 16 179 46
172 24 252 231 60 55 202 81 221 41 106 55 187 211 94 71 155 108 97 39 221 16
135 276 58 289 61 598 150 230 151 139 43 35 38 63 25 341 24 26 200 79 139 69
68 51 509 78 24 55 76 182 90 156 135 65 51 121 300 461 9 57 178 23 79 105 15
970 43 506 16 97 15 915 63 54 72 204 187 109 291 49 51 357 87 234 34 312 56
104 79 139 100 75 396 79 19 195 294 32 65 301 121 101 190 186 204 2 49 146 284
74 25 47 34 219 98 48 151 435 196 175 144 59 177 210 97 58 48 104 150 257 31
46 30 32 32 107 41 26 87 146 73 70 199 25 22 38 88 128 19 24 173 93 51 63 50
246 41 157 65 16 132 288 70 109 221 86 68 176 40 211 270 17 14 287 83 101 27
575 83 28 60 351 11 85 84 45 13 31 246 42 390 109 51 45 103 309 83 4 134 14 97
74 89 136 21 71 169 91 224 264 135 147 19 59 16 108 33 172 140 28 215 190 420
137 33 26 209 12 30 292 219 59 9 101 384 214 216 162 105 166 91 356 186 233
244 133 106 110 54 41 32 291 92 34 84 618 16 43 98 125 217 427 30 278 57 54 47
64 17 141 29 176 25 49 262 52 398 138 176 270 78 218 230 160 135 25 161 47 10
58 420 236 142 21 408 23 285 603 86 47 20 97 53 156 184 237 6 245 247 49 343
69 201 144 151 119 102 64 119 75 45 392 139 33 117 18 11 138 511 110 70 122 52
106 186 124 24 95 248 425 601 59 75 50 207 59 60 201 83 117 140 187 25 33 126
87 84 675 29 146 66 17 126 73 11 262 515 181 89 52 136 31 140 48 41 300 76 584
105 219 191 143 99 539 197 252 313 126 60 35 28 300 232 255 192 29 122 268 80
218 28 6 72 106 54 116 33 66 216 136 19 98 21 80 273 48 156 93 73 242 152 42
140 13 106 20 154 109 94 129 266 56 482 53 135 514 106 34 224 38 204 82 55 120
207 203 47 137 143 88 98 38 70 62 413 241 44 91 29 11 209 205 117 434 260 25
159 12 140 356 749 34 149 45 60 65 46 43 160 151 31 167 18 14 140 123 65 24 88
91 21 368 63 145 140 201 59 94 379 47 120 114 208 360 180 98 64 56 108 41 146
46 151 445 49 82 227 261 66 201 282 121 176 51 20 41 41 100 455 26 6 40 37 34
324 369 55 43 185 84 15 118 44 85 83 6 298 211 202 39 143 30 146 192 128 59 72
88 30 80 104 495 183 27 164 648 302 107 138 22 21 221 244 68 18 229 780 177 20
63 9 49 320 53 33 184 395 118 153 163 191 88 77 151 191 136 288 111 13 80 157
89 184 129 306 8 116 508 238 256 31 388 39 214 138 69 256 35 83 18 6 139 269
33 217 177 292 151 37 9 122 34 36 165 123 31 156 23 55 98 45 41 1108 198 233
169 85 81 110 27 343 77 121 213 232 344 87 354 16 247 41 36 21 41 173 25 361
93 114 97 10 65 29 87 168 141 89 136 82 10 120 88 9 88 35 199 223 67 185 445
274 126 22 19 20 167 39 76 50 157 218 108 45 109 200 56 335 18 89 177 59 332
147 136 36 38 81 150 94 28 109 61 108 32 89 55 106 86 228 46 205 33 53 91 359
67 36 232 89 21 173 234 62 93 47 8 192 22 226 96 113 74 189 83 140 38 200 1009
104 74 95 134 17 345 240 121 8 25 81 243 33 23 47 168 55 48 72 12 51 112 81 54
143 334 19 54 214 513 444 64 48 289 132 211 56 344 11 201 54 24 115 514 48 14
97 9 371 29 23 448 101 43 25 130 36 221 125 413 59 42 439 19 105 387 98 228 63
194 21 302 116 228 146 180 237 29 343 161 8 227 72 66 52 69 200 87 312 393 105
56 61 132 88 17 312 186 38 84 222 29 443 148 112 176 8 11 111 142 112 211 283
337 194 26 107 355 53 91 34 196 23 182 168 138 35 41 233 55 138 75 45 480 86
97 294 61 35 337 222 386 143 57 30 24 180 13 92 15 414 10 40 66 13 428 60 529
373 123 107 31 58 116 225 99 182 130 61 67 53 154 404 215 46 272 10 257 309 23
232 153 27 118 357 218 128 64 61 63 417 264 62 161 36 33 109 338 76 53 315 57
15 219 41 28 20 113 134 17 9 725 67 64 300 214 33 13 139 388 274 230 16 137 49
74 21 232 39 150 164 121 616 108 102 112 24 174 84 289 109 305 268 99 95 279
351 16 6 25 283 82 81 532 171 337 57 49 387 188 70 64 50 166 50 47 73 101 259
24 221 117 38 143 149 75 138 101 332 26 158 115 70 162 314 366 81 18 120 257
252 20 241 184 45 195 123 134 76 335 73 181 216 174 103 222 74 36 99 338 106
39 327 157 279 345 123 8 31 176 120 63 298 259 31 190 398 88 37 104 141 169
335 20 138 178 87 26 54 43 96 66 108 157 284 84 132 185 15 364 342 42 6 198
116 33 33 35 65 133 99 31 66 67 36 58 79 147 418 27 40 34 72 29 644 266 164 16
10 397 157 90 63 74 537 29 167 23 388 60 98 9 399 154 759 120 154 70 11 45 51
38 65 79 32 105 287 47 262 138 162 157 6 84 192 363 34 120 171 32 149 217 11
65 196 176 31 217 80 103 153 202 92 99 61 453 64 22 81 41 22 371 10 174 271
291 172 62 256 33 11 112 122 116 169 114 23 70 58 296 149 39 196 48 114 23 270
101 18 100 142 8 82 155 76 11 211 50 45 386 105 77 79 192 237 77 358 213 127
242 56 46 57 347 849 188 401 28 82 328 279 150 30 77 60 308 4 193 16 41 28 150
34 21 272 98 151 51 164 43 112 489 73 47 22 33 10 90 7 41 54 492 124 50 71 371
393 150 592 109 602 75 89 160 162 95 68 637 10 371 184 145 527 82 402 31 38
169 82 256 252 318 207 180)