论文标题
算术子序列在加性集的随机排序中
Arithmetic subsequences in a random ordering of an additive set
论文作者
论文摘要
对于有限套$ a $ a $ n $的$ a $ n $，订购是从$ \ {1,2，\ ldots，n \}到$ a $的注入。我们介绍了有关最长算术子序列的长度$ l_n $的渐近属性的结果，该属性是在随机排序中添加添加剂集$ a $ a $的结果。在无扭矩的情况下，其中$ a = [1，n]^d \ subseteq {\ bf z}^d $，我们证明$ l_n \ sim 2d \ log n/\ log n/\ log log \ log n $。我们表明，情况$ a = {\ bf z}/n {\ bf z} $表现得像无扭转的情况一样渐近，$ d = 1 $，然后使用此事实来计算随机订购的最长算术算法的预期长度。我们还证明，$ {\ bf z}/n {\ bf z} $的订购数，而没有任何算术子序列$ 3 $ 3 $的$ 2^{n-1} $当$ n \ geq 2 $是$ 2 $的幂时，否则为零。我们以对基本$ p $ groups的具体申请进行结论，并讨论可能的非交通概括。
For a finite set $A$ of size $n$, an ordering is an injection from $\{1,2,\ldots,n\}$ to $A$. We present results concerning the asymptotic properties of the length $L_n$ of the longest arithmetic subsequence in a random ordering of an additive set $A$. In the torsion-free case where $A = [1,n]^d\subseteq {\bf Z}^d$, we prove that $L_n\sim 2d\log n/\log\log n$. We show that the case $A = {\bf Z}/n{\bf Z}$ behaves asymptotically like the torsion-free case with $d=1$, and then use this fact to compute the expected length of the longest arithmetic subsequence in a random ordering of an arbitrary finite abelian group. We also prove that the number of orderings of ${\bf Z}/n{\bf Z}$ without any arithmetic subsequence of length $3$ is $2^{n-1}$ when $n\geq 2$ is a power of $2$, and zero otherwise. We conclude with a concrete application to elementary $p$-groups and a discussion of possible noncommutative generalisations.
