We prove 3SUM-hardness (no strongly subquadratic-time algorithm, assuming the 3SUM conjecture) of several problems related to finding Abelian square and additive square factors in a string. In particular, we conclude conditional optimality of the state-of-the-art algorithms for finding such factors. Overall, we show 3SUM-hardness of (a) detecting an Abelian square factor of an odd half-length, (b) computing centers of all Abelian square factors, (c) detecting an additive square factor in a length-$n$ string of integers of magnitude $n^{\mathcal{O}(1)}$, and (d) a problem of computing a double 3-term arithmetic progression (i.e., finding indices $i \ne j$ such that $(x_i+x_j)/2=x_{(i+j)/2}$) in a sequence of integers $x_1,\dots,x_n$ of magnitude $n^{\mathcal{O}(1)}$. Problem (d) is essentially a convolution version of the AVERAGE problem that was proposed in a manuscript of Erickson. We obtain a conditional lower bound for it with the aid of techniques recently developed by Dudek et al. [STOC 2020]. Problem (d) immediately reduces to problem (c) and is a step in reductions to problems (a) and (b). In conditional lower bounds for problems (a) and (b) we apply an encoding of Amir et al. [ICALP 2014] and extend it using several string gadgets that include arbitrarily long Abelian-square-free strings. Our reductions also imply conditional lower bounds for detecting Abelian squares in strings over a constant-sized alphabet. We also show a subquadratic upper bound in this case, applying a result of Chan and Lewenstein [STOC 2015].
翻译:我们证明了3SUM- 硬度( 没有强烈的次二次二次时间算法, 假设 3SUM猜想 ) 与在字符串中找到 Abelian 广场和添加性方方因数有关的数个问题 。 特别是, 我们得出了为找到此类因数而采用的最先进算法的有条件最佳性。 总的来说, 我们显示 3SUM- 硬度 (a) 检测到一个奇特半长的 Abel 方因数, (b) 所有 Abelian 方因数的计算中心, (c) 检测到一个在直径为 $+x_ 1, (d) 直径为x++j) 平方因数, (c) 在直径为 直径直的整数, (d) 在直径直值为 直径直的直值中, (c) 直径为直径直到直径直的平方位 。 (c) 直径直到直径直至直径直径直径直为平方列的平方列, (c) 直到直到直为直为直为直径直径直为直, 。 (c) 直为直为直为直为直为直为直为直为直, 直为直为直为直为直为直, 直为直为直为平方, 。