{'fraction_non_alphanumeric': 0.023792357606344627, 'fraction_numerical': 0.006308579668348954, 'mean_word_length': 4.340230991337825, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A one-to-two dimensional mapping using a partial fast Fourier transform

It will be shown how to map a simple one-dimensional tight binding model with a cosine potential in one dimension exactly to a two dimensional tight binding model with periodic boundary conditions with the presence of a single flux quantum spread evenly on the torus. The mapping is is achieved by a partial sequence of"Fast Fourier Transform"(FFT) steps which if completed would be an exact Fourier transform of the original model. Each step of the FFT recursively maps a tight binding model into two decoupled sublattices of half the lattice length.

I.

MOTIVATION
The following paper is dedicated to Nihat Berker and describes a mathematical curiosity that I stumbled across a few years ago. It brings together two ideas that were a daily topic of discussion with Nihat during my graduate student days: duality and renormalization.
The work also resulted from my admiration of the elegant recursive algorithms that lie at the basis of the efficient solution of a number of practical problems, most notably sorting and the Fourier transform.
For a transitionally invariant problem, a Fourier transform usually either solves or at least decouples the spatial degrees of freedom so that the original problem becomes simple.
When applied directly on data of length N it uses a number of operations that scale like N 2 . The "Fast Fourier Transform" (FFT) dramatically reduces the number of arithmetic operations using a clever recursive algorithm. An interesting question would be if if a single FFT recursion could somehow be the basis of a renormalization transformation that would partially decouple a problem at each stage of recursion. Ultimately I was not able to answer this question but in the process came up with a surprising result; that repeated application of the FFT recursion can map a problem from one to two dimensions.

II. BACKGROUND
Before proceeding to the calculation this I make a brief comment on the history of the The power of the FFT algorithm is that it dramatically reduces the number of arithmetic operations required for a Fourier transform of a large data set. For the most common "radix-2" algorithm the number of data points is taken to be L = 2 n . The number of operations will be on the order of 2nL rather than the L 2 number of operations that results from applying a simple matrix operation. The FFT algorithm can also be implemented on arbitrary length data where the number of arithmetic operations scales like L times the sum of prime factors of L. When L is prime, the FFT reduces to the ordinary matrix operation.
Without going into detail, I will now write down the key formulas using radix-2 algorithm that shows how the FFT is based on recursion. We begin with data x m where 0 ≤ m < L and L = 2 n . We define the Fourier transform The sum can be split into two parts: where e k can be seen to be the Fourier transform of the even indexed subset of x k and o k is the Fourier transform of the odd subset. This procedure can therefore be done recursively, splitting e k and o k successively into into odd and even subsets each with half as many data points.
This notation is clumsy and does not lend itself to recursion. To implement it systematically we must keep track of which order of even and odd blocks we use to construct x k as we apply the algorithm. We use the label c j,k keep track of our recursive indexing. We begin by defining c j,1 = x j to consist of the original data. The recursion then consists of breaking the 3 first index j into odd and even blocks. Since I will shortly write down a precise formula, I will first just the sketch the idea of constructing the indexing. We lay the "odd" and "even" blocks next to one another and put in a binary index "0" last if the block is even and "1" if the block is odd. The original block is periodic in length L; each new block is periodic in length L/2 and the number of blocks, say N in number is doubled to length 2N . Thus the original index (j, 1) will be replaced by an index (j , k) where the "block" index k encodes odd and even block and (j ) describes the new order in the subblock. Doing this recursively, the index k will gradually become the "frequency" or "momentum" index. The recursion is finished when the entire space index has been reduced to length one and the momentum index has become length L. [5] Let us use the notation r : L to denote the integer r modulo L. We encode the algorithm as follows: It is straightforward to apply this operation to quantum mechanical operators c r:L,s:N where c is simply the one particle (destruction) operator on an L × N lattice of "pseudo real space" dimension L and "pseudo k-space" dimension N . For the initial iteration L is the original space dimension, and N = 1. Equivalently we can simply interpret c r as the column vector being transformed and c † r as a row vector. Thus we begin with a periodic "real space" lattice of length 2 n to which we initially attach a bogus "momentum space" lattice of length 1 to begin the recursion with c j,1 . At each FFT step we halve the length of the real space and double the length of the momentum space.
Eventually when we are done applying the recursion n times the "real space" lattice will have shrunk to length one and the variables c 1,k that correspond to the momentum space lattice will be the Fourier transform of the original variables.
What if we stop this recursion "half way"? Provided L is 2 2m where m is integer, we will obtain a two dimensional periodic 2 m × 2 m lattice index when we stop the procedure after m recursions and thus will have obtained a mapping to a "two-dimensional" 2 m × 2 m index c j,k on a torus from our original 2 2m periodic index.

4
Clearly this transformation is highly nonlocal since it mixes Fourier components of indexes very far apart. If we start with an arbitrary real space operator written in terms of the real space operators c r and apply this prescription it is tempting to conclude that we will always get a terrible mess during the recursion. This is indeed true generically. However, we know that a transitionally invariant operator is diagonalized by the Fourier transform, i.e.
written as a simple local operator in the fully transformed basis. Thus eventually after recursion the momentum space blocks must decouple and the intuition that the problem gets more and more intractable under recursion is violated. Furthermore, a model which is invariant under Fourier transform should be symmetric in momentum and space coordinates half way through the recursion, so perhaps such a model will retain a structure during the intermediate steps of the recursion as well. It is precisely question we will explore further by example.
In the rest of this communication, I will focus on the following model under the "partial" FFT operation. We begin with This is in fact a special case of "Harper's model" where periodicity is exactly one relative to the length of the lattice. [6] a point which I will discuss at the end of this paper.
We know that the first term transforms to the cosine under Fourier transform and vice versa. For this choice of parameters the model is "self dual" i.e. transforms to itself under Fourier transform. It can therefore be expected to be symmetric in some way when partially transformed n times, where 2 2n = L. For illustration, we begin with a 64 × 1 lattice and apply the FFT step three times to transform this model numerically to an 8 × 8 lattice. The result of applying this transformation is given by the following Hamiltonian where δ are only nearest neighbor lattice vectors, where |t r,δ | = t and the phases of t correspond to a single flux evenly spread throughout the entire lattice. [7] The value of t r,r = e 2πin r,r /64 where n r,r is shown in Fig. 1.
The vertical bonds with phase zero represent the mapping of the cosine potential, whereas the horizontal bonds that carry the flux is the transformation of the hopping. It is interesting to compare the eigenstates of the tight binding model to the corresponding states mapped by the partial FFT. The absolute square of the six lowest eigenstates ψ j of of h 256×1 is plotted in Fig. 2. These corresponding eigenstates of h 16 is plotted in Fig. 3 and thus represents the "2-D" mapping of the "1-D" states in Fig. 2

Connection to Harper's equation
It is well known that an infinite two-dimensional tight binding model in a constant magnetic field maps to a one tight binding model with a periodic or quasiperiodic potential. In addition to P.G. Harper's paper mentioned previously, there are several other early classic papers on listed in the references. [8] In 1976, R. Hofstadter's performed a numerical analysis of the problem and pointed out the beautiful self-similar structure of the energy spectrum. [9] A number of paper followed in the 80's that explored this using renormalization group ideas. [10] The extent to which these are pertinent to the present problem is addressed in this section.
For a tight-binding model in the presence of a magnetic field with flux α/2π per plaquette we can introduce a Landau gauge and write the Hamiltonian as where t r,±ŷ = t and t r,∓x = t exp(±iπαy). Noting the invariance of the problem for translations along the x-direction we introduce plane waves along the x axis and define c mx+nŷ = e iνmc n resulting in a Hamiltonian forc n of the form in If we demand that this Hamiltonian be periodic with period q we find that that α = p/q is the ratio of integers. The flux per square in the 2-D problem Eq. 5 is thus a integral multiple of 2π/q. Is this the transformation we have been doing in the previous section?
If we begin with a p × p periodic two-dimensional lattice and add a constant magnetic field described in Landau gauge, we find that ν must obey ν = 2πm/p with m integer and we with flux and periodicity reduced from the ordinary formulation of that problem.

Further work
These proceedings has provided an opportunity to publish work which I find interesting but admittedly incomplete. When performing the recursion on the tight binding model 7 only, each FFT recursion decouples the spatial degrees of freedom into two coupled blocks.
My original hope was that these transformation might be the basis of a renormalization transformation; if an interaction could be found that was similarly decoupled, a novel way to solve an interacting model would be found. Unfortunately this goal has not been fulfilled but perhaps someone might be motivated to look at this problem again with the observations presented here.

Acknowledgment
I thank Nihat Berker for being my friend, mentor and collaborator during my first three years as a graduate student at Harvard. His boundless energy and enthusiasm helped make these years very happy and productive. I also thank him for putting the necessary friendly pressure on me to write up this contribution for these proceedings. I also thank the referee for making several pertinent and important comments that clarified the relation to Harper's equation.