Abstract. Given [Formula: see text] points [Formula: see text] on the unit circle in [Formula: see text] and a number [Formula: see text], we investigate the minimizers of the functional [Formula: see text]. While it is known that each of these minimizers is a spanning set for [Formula: see text], less is known about their number as a function of [Formula: see text] and [Formula: see text] especially for relatively small [Formula: see text]. In this paper we show that there is unique minimum for this functional for all [Formula: see text] and all odd [Formula: see text]. In addition, we present some numerical results suggesting the emergence of a phase transition phenomenon for these minimizers. More specifically, for [Formula: see text] odd, there exists a sequence of points [Formula: see text] so that a unique (up to some isometries) minimizer exists on each of the subintervals [Formula: see text].

Fingerprinting is a widely-used technique for efficiently verifying that two files are identical. More generally, linear sketching is a form of lossy compression (based on random projections) that also enables the "dissimilarity" of non-identical files to be estimated. Many sketches have been proposed for dissimilarity measures that decompose coordinate-wise such as the Hamming distance between alphanumeric strings, or the Euclidean distance between vectors. However, virtually nothing is known on sketches that would accommodate alignment errors. With such errors, Hamming or Euclidean distances are rendered useless: a small misalignment may result in a file that looks very dissimilar to the original file according such measures. In this paper, we present the first linear sketch that is robust to a small number of alignment errors. Specifically, the sketch can be used to determine whether two files are within a small Hamming distance of being a cyclic shift of each other. Furthermore, the sketch is homomorphic with respect to rotations: it is possible to construct the sketch of a cyclic shift of a file given only the sketch of the original file. The relevant dissimilarity measure, known as the shift distance, arises in the context of embedding edit distance and our result addressed an open problem [Question 13 in Indyk-McGregor-Newman-Onak'11] with a rather surprising outcome. Our sketch projects a length $n$ file into D(n) ⋅ polylog n dimensions where D(n)l n is the number of divisors of n. The striking fact is that this is near-optimal, i.e., the D(n) dependence is inherent to a problem that is ostensibly about lossy compression.