akc.is / inv-mono
The inversion monotonicity conjecture
The celebrated Marcus-Tardos Theorem (2004) states: For every \(\tau\in\mathfrak{S}_{\ell}\) there is a constant \(C=C(\tau)\) such that \(|\mathfrak{S}_n(\tau)| \leq C^n\) for all \(n\geq 0\). This used to be known as the Stanley-Wilf conjecture and the constant \[ L(\tau) = \lim_{n\to\infty}{|\mathfrak{S}_n(\tau)|^{1/n}} \] is known as the Stanley-Wilf limit for \(\tau\). The smallest pattern \(\tau\) for which \(L(\tau)\) is unknown is \(\tau=1324\). The current records for lower and upper bounds on \(L(1324)\) are both due to Bevan, Brignall, Price and Pantone (2020): \(10.271 < L(1324) < 13.5\)
Let us say that a pattern \(\tau\) is inversion-monotone, or inv-monotone for short, if \[ |\{\pi\!\in\!\mathfrak{S}_n(\tau)\!: \mathrm{inv}(\pi)\!=\!k\}| \;\leq\; |\{\pi\!\in\!\mathfrak{S}_{n+1}(\tau)\!: \mathrm{inv}(\pi)\!=\!k\}| \] That is, among \(\tau\)-avoiding permutations with exactly \(k\) inversions there are at least as many of length \(n+1\) as there are of length \(n\). For instance, \(\tau=132\) is inv-monotone as is witnessed by the inversion preserving injection \(\pi \mapsto \pi\oplus 1\). More generally, any pattern \(\tau\in\mathfrak{S}_{\ell}\) such that \(\tau(1)>1\) or \(\tau(\ell)<\ell\) is trivially inv-monotone.
Consider the following deceptively simple conjecture.
Conjecture (Claesson, Jelínek and Steingrímsson): The pattern 1324 is inv-monotone.
If you can prove this conjecture then you would also set a new record for the upper bound of \(L(1324)\): If the conjecture is true, then \[ L(1324) \;\leq\; e^{\pi\sqrt{2/3}}\;\simeq\; 13.001954. \] Below is a table for the distribution of inversions over 1324-avoiding permutations. In the \(n\)th row and \(k\)th column you find the number 1324-avoiding permutation of \(\{1,2,\ldots,n\}\) with exactly \(k\) inversions, where \(n,k\leq 47\). This data was produced by Bjarki Ágúst Guðmundsson and myself. In terms of this table, or rather an infinite ideal version of it, the conjecture above claims that the columns are weakly increasing.
Linusson and Verkama have recently proved that the conjecture holds under the additional assumption that \(n\geq (k+7)/2\).
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 5 6 5 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 5 10 16 20 20 15 9 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 5 10 20 32 51 67 79 80 68 49 29 14 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 5 10 20 36 61 96 148 208 268 321 351 347 308 241 165 98 49 20 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 5 10 20 36 65 106 171 262 397 568 784 1019 1264 1478 1628 1681 1619 1441 1173 866 574 338 174 76 27 7 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 5 10 20 36 65 110 181 286 443 664 985 1416 1988 2715 3589 4579 5631 6654 7559 8225 8545 8457 7930 7006 5794 4448 3146 2034 1190 622 285 111 35 8 1 0 0 0 0 0 0 0 0 0
1 2 5 10 20 36 65 110 185 296 467 714 1077 1582 2305 3284 4617 6374 8665 11521 15012 19067 23599 28426 33300 37862 41767 44597 46031 45814 43837 40194 35164 29200 22886 16825 11525 7305 4249 2244 1061 440 155 44 9 1
1 2 5 10 20 36 65 110 185 300 477 738 1127 1682 2477 3584 5134 7240 10100 13915 18976 25563 34017 44640 57739 73421 91706 112369 134995 158843 182924 206000 226726 243633 255287 260495 258437 248816 231917 208703 180729 150024 118859 89438 63590 42483
1 2 5 10 20 36 65 110 185 300 481 748 1151 1732 2577 3768 5450 7766 10976 15312 21171 28973 39338 52919 70657 93482 122650 159379 205068 260922 328043 406988 497946 600332 712814 833046 957754 1082618 1202737 1312433 1405748 1476811 1520435 1532418 1510261 1453332
1 2 5 10 20 36 65 110 185 300 481 752 1161 1756 2627 3868 5634 8098 11526 16216 22632 31266 42845 58213 78531 105137 139867 184814 242710 316693 410669 528943 676748 859401 1082745 1352295 1673211 2049259 2483103 2975033 3522944 4121303 4761111 5429597 6110716 6784483
1 2 5 10 20 36 65 110 185 300 481 752 1165 1766 2651 3918 5734 8282 11858 16786 23568 32768 45234 61902 84130 113477 152101 202507 268085 352792 461873 601434 779378 1004933 1289658 1646934 2093048 2646379 3328246 4161918 5172714 6386373 7828508 9522733 11489526 13743958
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2661 3942 5784 8382 12042 17118 24138 33728 46776 64346 87939 119306 160848 215461 286965 379951 500446 655656 854909 1109409 1433363 1843853 2362403 3014567 3832210 4853039 6123185 7696477 9637475 12020188 14931099 18466282
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3952 5808 8432 12142 17302 24470 34298 47736 65916 90431 123184 166825 224482 300396 399677 529060 696635 912963 1190716 1546182 1998983 2573979 3301057 4217831 5369411 6811907 8612799 10855057 13637971 17082759 21333456
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5818 8456 12192 17402 24654 34630 48306 66876 92001 125708 170759 230542 309593 413434 549339 726213 955573 1251487 1631943 2118852 2739960 3528981 4528200 5788897 7374868 9363215 11849304 14948081 18800883 23577579
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8466 12216 17452 24754 34814 48638 67446 92961 127278 173283 234512 315717 422728 563300 746870 985792 1295195 1694545 2207615 2864727 3702764 4768303 6117967 7822525 9967819 12660449 16029173 20232832 25463095
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12226 17476 24804 34914 48822 67778 93531 128238 174853 237036 319687 428892 572666 760942 1006681 1325844 1738982 2271465 2955545 3830867 4947460 6366580 8164866 10435923 13295958 16886403 21381871 26994017
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17486 24828 34964 48922 67962 93863 128808 175813 238606 322211 432862 578830 770352 1020833 1346858 1769891 2316384 3020212 3923083 5077862 6549439 8419397 10787550 13778465 17544055 22272580 28192959
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24838 34988 48972 68062 94047 129140 176383 239566 323781 435386 582800 776516 1030243 1361058 1790993 2347432 3065419 3988284 5170983 6681389 8604799 11046173 14136594 18036712 22945863 29107595
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 34998 48996 68112 94147 129324 176715 240136 324741 436956 585324 780486 1036407 1370468 1805193 2368586 3096563 4033644 5236500 6775096 8737742 11233273 14398004 18399323 23445634 29791940
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49006 68136 94197 129424 176899 240468 325311 437916 586894 783010 1040377 1376632 1814603 2382786 3117717 4064844 5281964 6840780 8831793 11366854 14586185 18662581 23811276 30296583
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68146 94221 129474 176999 240652 325643 438486 587854 784580 1042901 1380602 1820767 2392196 3131917 4085998 5313164 6886304 8897589 11461086 14720138 18851452 24075703 30664223
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94231 129498 177049 240752 325827 438818 588424 785540 1044471 1383126 1824737 2398360 3141327 4100198 5334318 6917504 8943113 11526946 14814490 18985600 24264974 30929392
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129508 177073 240802 325927 439002 588756 786110 1045431 1384696 1827261 2402330 3147491 4109608 5348518 6938658 8974313 11572470 14880350 19080020 24399250 31118872
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177083 240826 325977 439102 588940 786442 1046001 1385656 1828831 2404854 3151461 4115772 5357928 6952858 8995467 11603670 14925874 19145880 24493670 31253220
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240836 326001 439152 589040 786626 1046333 1386226 1829791 2406424 3153985 4119742 5364092 6962268 9009667 11624824 14957074 19191404 24559530 31347640
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326011 439176 589090 786726 1046517 1386558 1830361 2407384 3155555 4122266 5368062 6968432 9019077 11639024 14978228 19222604 24605054 31413500
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439186 589114 786776 1046617 1386742 1830693 2407954 3156515 4123836 5370586 6972402 9025241 11648434 14992428 19243758 24636254 31459024
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589124 786800 1046667 1386842 1830877 2408286 3157085 4124796 5372156 6974926 9029211 11654598 15001838 19257958 24657408 31490224
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786810 1046691 1386892 1830977 2408470 3157417 4125366 5373116 6976496 9031735 11658568 15008002 19267368 24671608 31511378
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046701 1386916 1831027 2408570 3157601 4125698 5373686 6977456 9033305 11661092 15011972 19273532 24681018 31525578
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386926 1831051 2408620 3157701 4125882 5374018 6978026 9034265 11662662 15014496 19277502 24687182 31534988
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831061 2408644 3157751 4125982 5374202 6978358 9034835 11663622 15016066 19280026 24691152 31541152
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408654 3157775 4126032 5374302 6978542 9035167 11664192 15017026 19281596 24693676 31545122
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157785 4126056 5374352 6978642 9035351 11664524 15017596 19282556 24695246 31547646
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157789 4126066 5374376 6978692 9035451 11664708 15017928 19283126 24696206 31549216
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157789 4126070 5374386 6978716 9035501 11664808 15018112 19283458 24696776 31550176
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157789 4126070 5374390 6978726 9035525 11664858 15018212 19283642 24697108 31550746
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157789 4126070 5374390 6978730 9035535 11664882 15018262 19283742 24697292 31551078
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157789 4126070 5374390 6978730 9035539 11664892 15018286 19283792 24697392 31551262
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157789 4126070 5374390 6978730 9035539 11664896 15018296 19283816 24697442 31551362
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157789 4126070 5374390 6978730 9035539 11664896 15018300 19283826 24697466 31551412
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157789 4126070 5374390 6978730 9035539 11664896 15018300 19283830 24697476 31551436
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157789 4126070 5374390 6978730 9035539 11664896 15018300 19283830 24697480 31551446
1 2 5 10 20 36 65 110 185 300 481 752 1165 1770 2665 3956 5822 8470 12230 17490 24842 35002 49010 68150 94235 129512 177087 240840 326015 439190 589128 786814 1046705 1386930 1831065 2408658 3157789 4126070 5374390 6978730 9035539 11664896 15018300 19283830 24697480 31551450 As you can see each column is eventually constant and the sequence \(1,2,5,10,20,36,65,110,\dots\) that emerges is A000712. This part of the reason why the conjecture implies a new upper bound of \(L(1324)\).