{"id":"arxiv/2607.25381","url":"https://arxiv.org/abs/2607.25381","tags":["cs.FL","cs.CC","cs.DS","math.CO"],"score":0,"title":"Breaking the $4^k$ Barrier for the $k$-Distinct Language","domain":"cs.FL","source":"arxiv","authors":["Ran Ben Basat"],"reviews":0,"subject":"cs.FL","summary":"For integers $k\\le n$, let $L_{k,n}$ be the set of words over $[n]$ of length at most $k$ in which no symbol is repeated. We present a nondeterministic finite automaton (NFA) of size $3.918^k n^{O(1)}$, improving on the $4^{k+o(k)}n^{O(1)}$ construction of Ben-Basat, Gabizon, and Zehavi. Our proof organizes several classical ingredients---product automata, hashing, and coefficient estimates---into a gadget-amplification framework: We take the product of many copies of a small local NFA gadget, whose language is a subset of $L_{r,c}$, and hash the $k$ input symbols to copies and local colors.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-28","reactions":{}}