Improved Lower Bound on the Number of Pseudoline Arrangements

We show that for large enough n, the number of non-isomorphic pseudoline arrangements of order n is greater than 2c· n² for some constant $c > 0.2604$, improving the previous best bound of $c>0.2083$ by Dumitrescu and Mandal (2020). Arrangements of pseudolines (and in particular arrangements of lines) are important objects appearing in many forms in discrete and computational geometry. They have strong ties for example with oriented matroids, sorting networks and point configurations. Let Bₙ be the number of non-isomorphic pseudoline arrangements of order n and let bₙ := log₂(Bₙ). The problem of estimating bₙ dates back to Knuth, who conjectured that bₙ ≤ 0.5n² + o(n²) and derived the first bounds n²/6-O(n) ≤ bₙ ≤ 0.7924(n²+n). Both the upper and the lower bound have been improved a couple of times since. For the upper bound, it was first improved to bₙ < 0.6988n² (Felsner, 1997), then bₙ < 0.6571 n² by Felsner and Valtr (2011), for large enough n. In the same paper, Felsner and Valtr improved the constant in the lower bound to $c> 0.1887$, which was subsequently improved by Dumitrescu and Mandal to $c>0.2083$. Our new bound is based on a construction which starts with one of the constructions of Dumitrescu and Mandal and breaks it into constant sized pieces. We then use software to compute the contribution of each piece to the overall number of pseudoline arrangements. This method adds a lot of flexibility to the construction and thus offers many avenues for future tweaks and improvements which could lead to further tightening of the lower bound.