An Improved Lower Bound on the Number of Pseudoline Arrangements

Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years ago. The study of the number Bₙ of non-isomorphic simple arrangements of n pseudolines goes back to Goodman and Pollack, Knuth, and others. It is known that Bₙ is in the order of 2Θ(n²) and finding asymptotic bounds on bₙ = log₂(Bₙ)/n² remains a challenging task. In 2011, Felsner and Valtr showed that 0.1887 ≤ bₙ ≤ 0.6571 for sufficiently large n. The upper bound remains untouched but in 2020 Dumitrescu and Mandal improved the lower bound constant to $0.2083$. Their approach utilizes the known values of Bₙ for up to $n=12$. We tackle the lower bound with a dynamic programming scheme. Our new bound is bₙ ≥ 0.2526 for sufficiently large n. The result is based on a delicate interplay of theoretical ideas and computer assistance.