text:
# De Bruijn Cycles for Covering Codes

## 1 Introduction

A covering code $`𝒞`$ of radius $`R`$ and dimension $`n`$ on $`q`$ symbols is a subset of the space $`[q]^n`$ such that every string in $`[q]^n`$ differs from some element of $`𝒞`$ in at most $`R`$ coordinates. It is common to require that $`R`$ be as small as possible in the definition of a covering code, but, for the sake of notational convenience, we do not require this here.

Question: Given $`n`$, $`R`$, and $`q`$, what is the smallest $`M=M(n,R,q)`$ so that there exists an $`q`$-ary string $`S=(s_0,\mathrm{},s_{M1})`$ with the property that the set of $`n`$-strings appearing as $`(s_i,\mathrm{},s_{i+n1})`$, with indices taken modulo $`M`$, form a covering code of radius $`R`$? Call such a string a $`(n,R,q)`$-de Bruijn covering code.

For example, $`111000`$ is a $`(4,1,2)`$-de Bruijn covering code, because every binary $`4`$-string is at most one bit change from an element of

$$\{1110,1100,1000,0001,0011,0111\}.$$

On the alphabet $`\{\text{A,G,T,C}\}`$, the string

AGATCGCAGATATGGTCTATG
is a $`(4,2,4)`$-de Bruijn covering code, by Proposition 6 below.

Clearly, $`M(n,0,q)=q^n`$, since any de Bruijn covering code of radius $`0`$ is actually a de Bruijn cycle, and de Bruijn cycles of all orders over an arbitrary alphabet exist. (See, for example, .) If we fix $`R>0`$ and $`q2`$, how does $`M(n,R,q)`$ grow as $`n\mathrm{}`$?

It is easy to see that the growth is at least $`\mathrm{\Omega }(q^n/n^R)`$, by the so-called “sphere-covering” bound. The set of strings which differ from any given $`S`$ in at most $`R`$ places has the same cardinality, $`_{k=0}^R\left(\genfrac{}{}{0pt}{}{n}{k}\right)(q1)^k`$. Therefore, if we are to cover all $`q^n`$ strings, we need at least

$$\frac{q^n}{_{k=0}^R\left(\genfrac{}{}{0pt}{}{n}{k}\right)(q1)^k}$$

codewords. On the other hand, it is well known that the size of the smallest $`q`$-ary covering code of radius $`R`$ actually achieves this bound, up to a multiplicative constant which depends on $`R`$ and $`q`$. (See  for the latest results on the size of this constant.) We may concatenate all the codewords of such a minimal code to yield a $`(n,R,q)`$-de Bruijn covering code of length $`O(q^n/n^{R1})`$. This construction is clearly very wasteful, however. Can we do better, i.e., is the true order of magnitude of $`M(n,R,q)`$ closer to the sphere-covering bound? In particular, can we say something nontrivial in the case of $`R=1`$? In fact, in Section 3 we prove the following.

###### Theorem 1.

For each $`n`$ and $`q`$ a prime power, there exists a $`(n,R,q)`$-de Bruijn covering code of length $`(R+1+o(1))q^n\mathrm{log}n/(\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R)`$.

Section 2 states several definitions and preliminary results we will need to prove this. The next section contains the proof itself, and Section 4 introduces a “spectral” perspective on de Bruijn covering codes that holds some independent interest. In Section 5 we present bounds for special values of $`n`$, $`R`$, and $`q`$, and include a table of bounds on $`M(n,R,2)`$ for $`2n13`$ and $`1R11`$. We end with several remarks and questions for further work in Section 6.

## 2 Preliminaries

We fix a prime power $`q2`$ throughout this section and the next, and take our alphabet to be $`𝔽_q`$. (If $`q`$ is not a prime power, we take the alphabet to be $`/q`$.) Write $`b_R(v)`$, for $`v`$ an $`n`$-string drawn from $`𝔽_q`$, to denote the set of those strings differing from $`v`$ in at most $`R`$ coordinates. That is, $`b_R(v)`$ is $`v`$’s radius $`R`$ neighborhood in the Hamming metric. Also, write $`\text{wt}(v)`$ for the Hamming weight of the vector $`v`$, the number of nonzero symbols it contains.

Let $`\alpha `$ be a generator of the multiplicative group of the finite field $`𝔽_{q^n}`$. Denote by $``$ the elementary basis for $`𝔽_q^n`$ over $`𝔽_q`$. Given a basis $`=\{b_1,\mathrm{},b_n\}`$ of $`𝔽_{q^n}`$ over $`𝔽_q`$ and an element $`\gamma 𝔽_{q^n}`$, write $`f_{}(\gamma )`$ for the element of $`𝔽_q^n`$ whose $`j^{\text{th}}`$ coordinate is the coefficient of $`b_j`$ in the $``$-representation of $`\gamma `$. Then, given a nonzero vector $`𝐱𝔽_q^n`$, define $`\mathrm{\Lambda }(\alpha ,,𝐱)`$ to be the string whose $`j^{\text{th}}`$ coordinate (i.e., $`\mathrm{\Lambda }_j(\alpha ,,𝐱)`$, $`1jq^n1`$) is $`𝐱^{}f_{}(\alpha ^j)`$. It is well known that, when $`=\{\alpha ^j:0jn1\}`$ and $`\text{wt}(𝐱)=1`$, $`\mathrm{\Lambda }(\alpha ,,𝐱)`$ is a de Bruijn cycle of order $`n`$ if we insert a $`0`$ at the beginning. (See, for example, .) We generalize this result as follows. Define $`\mathrm{\Lambda }^{}(\alpha ,,𝐱)`$ to be the sequence $`\mathrm{\Lambda }(\alpha ,,𝐱)`$ with a zero inserted at the beginning of each occurrence of the string $`0\mathrm{}01`$. Then we have the following.

###### Proposition 2.

Fix a basis $``$ of $`𝔽_q^n`$ over $`𝔽_q`$, a generator $`\alpha 𝔽_{q^n}^\times `$, and a vector $`𝐱𝔽_q^n`$, and write $`\mathrm{\Phi }(j)`$ for the vector

$$(\mathrm{\Lambda }_j(\alpha ,,𝐱),\mathrm{},\mathrm{\Lambda }_{j+n1}(\alpha ,,𝐱))^{}𝔽_q^n$$

The map $`\mathrm{\Psi }`$ which sends $`0`$ to $`0`$ and $`\alpha ^j`$ to $`\mathrm{\Phi }(j)`$ is an isomorphism from the additive group of $`𝔽_{q^n}`$ to $`𝔽_q^n`$.

###### Proof.

First, we show that $`\mathrm{\Psi }`$ is linear. Write $`e_j`$ for the elementary $`n`$-vector whose coordinates are all zero except for a $`1`$ in the $`j^{\text{th}}`$ coordinate. We denote by $`M_{\gamma ,}`$ the matrix representing multiplication by $`\gamma 𝔽_{q^n}`$ in the $``$ basis. It is easy to see that

$$\mathrm{\Lambda }_j(\alpha ,,𝐱)=𝐱^{}f_{}(\alpha ^j)$$

and therefore that

$$\mathrm{\Psi }(\gamma )=\underset{j=0}{\overset{n1}{}}e_{j+1}𝐱^{}f_{}(\alpha ^j\gamma )=\underset{j=0}{\overset{n1}{}}e_{j+1}𝐱^{}M_{\alpha ,}^jf_{}(\gamma ),$$
(1)
which is obviously linear.

Now, suppose that $`\mathrm{\Psi }(\gamma )=0`$. We show that $`\gamma =0`$. Indeed, suppose that $`\{j_1,\mathrm{},j_n\}`$ are $`n`$ distinct integers so that $`\mathrm{\Lambda }_{j_i}(\alpha ,,𝐱)=0`$ for each $`i`$. If we denote by $`S`$ the subspace of $`𝔽_q^n`$ orthogonal to $`𝐱`$, then we have $`\alpha ^{j_i}f_{}^1(S)`$ for each $`i`$. However, $`f_{}`$ is linear and has a trivial kernel, so all the $`\alpha ^{j_i}`$ lie in a subspace of $`𝔽_q^n`$ of dimension $`n1`$ and are therefore linearly dependent. If we take $`j_i=j+i`$ for some $`j`$ (i.e., $`\mathrm{\Psi }(\gamma )=0`$ with $`\gamma =\alpha ^j`$), then we have that $`\{\alpha ^i\}_{i=j+1}^{j+n}`$ is a dependent set. Since $`M_{\alpha ,}`$ is nonsingular, this implies that $`\{\alpha ^i\}_{i=0}^{n1}`$ is a dependent set. But then we have

$$\underset{i=0}{\overset{n1}{}}c_i\alpha ^i=0$$

for some nonzero $`(c_1,\mathrm{},c_n)`$, so $`\alpha `$ satisfies a polynomial identity of degree less than $`n`$. Since $`\alpha `$ generates $`𝔽_{q^n}^\times `$, this implies that $`\{\alpha ^j\}_{j=0}^d`$ is a basis for $`𝔽_{q^n}`$ for some $`d<n1`$, contradicting the fact that the dimension of $`𝔽_{q^n}`$ over $`𝔽_q`$ is $`n`$. We can therefore conclude that $`\gamma =0`$. ∎

Note that the map $`\gamma M_{\gamma ,}`$ is actually an isomorphism of fields. The image is a set of matrices which form a field, i.e., a matrix field. These objects have been studied extensively and thoroughly characterized when the matrices take their entries from a finite field ().

###### Corollary 3.

$`\mathrm{\Lambda }^{}(\alpha ,,𝐱)`$ is a de Bruijn cycle.

###### Proof.

By the above argument, $`\mathrm{\Lambda }(\alpha ,,𝐱)`$ contains all nonzero $`n`$-strings. Clearly, the insertion of a $`0`$ causes the occurrence of the all-zeroes string without disrupting the presence of any other string. ∎

Our approach is to find an $`\alpha 𝔽_{q^n}`$, a basis $``$, and a vector $`𝐱`$ so that the first $`Kq^n\mathrm{log}n/(\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R)`$ length $`n`$ strings appearing in $`\mathrm{\Lambda }(\alpha ,,𝐱)`$ are (almost) a covering code of radius $`R`$. Specifically, we wish to show that, for only a small fraction of all $`v𝔽_{q^n}`$,

$$(v+B_R(0^n))\mathrm{\Psi }(\{\alpha ^j\}_{j=1}^K)=\mathrm{}$$

where $`\mathrm{\Psi }`$ is the function defined in Proposition 2. Define $`\mathrm{\Psi }^{}=f_{}\mathrm{\Psi }^1`$. Setting $`w=\mathrm{\Psi }^1(v)`$, we may bound this quantity from above by asking the number of $`w`$ so that

$$\mathrm{\Psi }^{}\left(\left(\genfrac{}{}{0pt}{}{}{R}\right)\right)f_{}(w+\{\alpha ^j\}_{j=1}^K)=\mathrm{}$$

which, by (1), is the same as saying that

$$\{\left(\underset{j=0}{\overset{n1}{}}e_{j+1}𝐱^{}M_{\alpha ,}^j\right)^1v:\text{wt}(v)=R\}f_{}(w+\{\alpha ^j\}_{j=1}^K)=\mathrm{}.$$

We must determine which matrices may appear in the form of the left-hand term. First, a result from linear algebra is needed. The following theorem appears in . A non-derogatory matrix is one whose eigenspaces are all one-dimensional, and a matrix in rational canonical form is comprised of blocks of the form

$$\begin{array}{cccccc}0& 0& 0& 0& \mathrm{}& a_1\\ 1& 0& 0& 0& \mathrm{}& \mathrm{}\\ 0& 1& 0& 0& \mathrm{}& \mathrm{}\\ 0& 0& 1& 0& \mathrm{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& \mathrm{}& \mathrm{}& \mathrm{}& 1& a_n\end{array}$$

along the diagonal.

###### Theorem 4.

If $`AK^{n\times n}`$ is non-derogatory and in rational canonical form, then the following are equivalent:

1. $`X`$ commutes with $`A`$.
2. The successive columns of $`X`$ are $`v`$, $`Av`$, …, $`A^{n1}v`$ for any $`vK^n`$.
3. There exists a polynomial $`gK[x]`$ so that $`X=g(A)`$.

Furthermore, $`g=_{j=0}^{n1}v_{j+1}x^j`$.

The matrices $`M_{\alpha ,}`$ are non-derogatory when $`\alpha `$ is a generator of $`𝔽_{q^n}`$, because their eigenvalues are all distinct, as the next result states.

###### Proposition 5.

A matrix $`M𝔽_q^{n\times n}`$ is of the form $`M_{\alpha ,}`$ for some generator $`\alpha 𝔽_{q^n}^\times `$ and basis $`𝔽_{q^n}`$ over $`𝔽_q`$ if and only if its eigenvalues (over the algebraic closure of $`𝔽_q`$) are $`\{\alpha ^{q^j}\}_{j=0}^{n1}`$.

###### Proof.

For a given $`\alpha `$, fix the basis $`𝒜=\{\alpha ^j\}_{j=0}^{n1}`$. Clearly, if we write $`B`$ for the matrix whose columns are $``$ written in the basis $`𝒜`$, then $`M_{\alpha ,}=B^1M_{\alpha ,𝒜}B`$. Therefore, a matrix $`M`$ is one of the desired ones if and only if it has the same eigenvalues as the matrix $`M_{\alpha ,𝒜}`$. Let $`p_\alpha (\lambda )`$ denote the characteristic polynomial of this matrix. By the Cayley-Hamilton Theorem (which applies to all commutative rings), $`p_\alpha (M_{\alpha ,𝒜})=0`$. However, the map $`\alpha M_{\alpha ,}`$ is an isomorphism of fields for any basis $``$. Therefore, $`p_\alpha (\alpha )=0`$. Since the Galois group of $`𝔽_{q^n}`$ over $`𝔽_q`$ is cyclic and generated by the Frobenius map $`xx^q`$, and the rest of the roots of $`p_\alpha `$ are the Galois conjugates of $`\alpha `$, the result follows. ∎

Furthermore, if we let $`\mathrm{\Theta }_\alpha `$ denote the basis $`\{\alpha ^j\}_{j=0}^{n1}`$, then $`M_{\alpha ,\mathrm{\Theta }_\alpha }`$ is in rational canonical form. Its $`j^{\text{th}}`$ column is $`e_{j+1}`$ for $`1jn1`$ and its $`n^{\text{th}}`$ column is the vector of coefficients of the minimal polynomial of $`\alpha `$ (without the leading term). Using this fact, we can prove the following from Theorem 4.

###### Lemma 6.

Fix a generator $`\alpha `$ of $`𝔽_{q^n}`$. Choose $`𝐱𝔽_q^n\{0^n\}`$ randomly and uniformly, and choose a basis $``$ randomly and uniformly. Then

$$\left(\underset{j=0}{\overset{n1}{}}e_{j+1}𝐱^{}M_{\alpha ,}^j\right)^1$$

is distributed uniformly over all invertible matrices.

###### Proof.

Evidently, it suffices to show that $`D(,𝐱)=_{j=0}^{n1}e_{j+1}𝐱^{}M_{\alpha ,}^j`$ is distributed uniformly. This matrix is one whose rows are $`𝐱^{}`$, $`𝐱^{}M_{\alpha ,}`$, $`\mathrm{}`$, $`𝐱^{}M_{\alpha ,}^{n1}`$. Write $`A`$ for the matrix $`M_{\alpha ,\mathrm{\Theta }_\alpha }`$ and $`P`$ for the matrix whose successive columns are the elements of $`\mathrm{\Theta }_\alpha `$ written in the $``$ basis, and write $`𝐲`$ for $`P^{}𝐱`$. Then we may also say that $`D(,𝐱)`$ is the matrix whose rows are $`𝐱^{}`$, $`𝐱^{}PAP^1`$, $`\mathrm{}`$, $`𝐱^{}PA^{n1}P^1`$, which we may rewrite as $`D(A,P^{}𝐱)P^1`$. Therefore, by Theorem 4 and the fact that $`A`$ is non-derogatory and in rational canonical form, $`D(,𝐱)=g_y(A)^{}P^1`$ with $`g_𝐲`$ denoting the polynomial whose coefficients are the entries of $`𝐲`$. Choosing $`𝐱`$ uniformly and randomly from the nonzero vectors yields the same distribution on $`𝐲`$, independent of the choice of $``$. Since $`A`$ is the image of $`\alpha `$ under the map $`\alpha M_{\alpha ,\mathrm{\Theta }_\alpha }`$, and $`g_y(\alpha )`$ is uniformly distributed over $`𝔽_{q^n}\{0\}`$ as $`𝐲`$ varies, we have $`g_y(A)`$ uniformly distributed over all matrices of the form $`M_{\gamma ,\mathrm{\Theta }_\alpha }`$ for $`\gamma 𝔽_{q^n}\{0\}`$. Choosing $``$ uniformly is the same as choosing $`P^1`$ uniformly, so we may conclude that $`D(,𝐱)=g_y(A)^{}P^1`$ is uniformly distributed over all invertible matrices.

## 3 The Main Result

It remains to show that the set of all sums of $`k`$ columns of a randomly, uniformly chosen invertible matrix are distributed more or less uniformly. Before proceeding, we need to state Suen’s Inequality. We follow . Let $`\{A_i\}_{iI}`$ be a set of events, and define a symmetric relation (i.e, a graph) $``$ on $`I`$. We say that $``$ is a superdependency graph if, whenever $`J_1,J_2I`$ have no edges between them, any Boolean combination of $`\{A_i\}_{iJ_1}`$ is independent of any Boolean combination of $`\{A_i\}_{iJ_2}`$. Write $`M=_{iI}\text{Pr}[\overline{A_i}]`$.

###### Theorem 7 (Suen’s Inequality).

Define

$$y(i,j)=(\text{Pr}[A_iA_i]+\text{Pr}[A_i]\text{Pr}[A_j])\underset{li\text{ or }lj}{}(1\text{Pr}[\overline{A_l}])^1.$$

Then

$$\text{Pr}\left[\underset{iI}{}\overline{A_i}\right]Me^{_{ij}y(i,j)}.$$

The following is a routine application of this result.

###### Proposition 8.

For $`R^+`$, if $`M`$ is chosen randomly and uniformly from $`GL_n(𝔽_q)`$, then, for any set $`S𝔽_q^n`$ with $`|S|=q^nK/(\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R)`$,

$$\text{Pr}\left[\{Mv:\text{wt}(v)=R\}S=\mathrm{}\right]e^K(c_q^1+o(1)).$$

where $`c_q=_{j=1}^{\mathrm{}}(1q^j)`$ and $`K=o(\sqrt{n})`$.

###### Proof.

The probability that a randomly, uniformly chosen invertible matrix has all sums of $`k`$ columns lying outside of a set $`S`$ is given by

$`\rho `$ $`=\text{Pr}[Mv\overline{S}\text{ when }\text{wt}(v)=R|MGL_n(𝔽_q)]`$
$`={\displaystyle \frac{\text{Pr}[(Mv\overline{S}\text{ when }\text{wt}(v)=R)(MGL_n(𝔽_q))]}{\text{Pr}[MGL_n(𝔽_q)]}}`$
$`{\displaystyle \frac{\text{Pr}[Mv\overline{S}\text{ when }\text{wt}(v)=R]}{\text{Pr}[MGL_n(𝔽_q)]}}`$
where we are choosing $`M`$ randomly and uniformly from all matrices. It is well known that $`|GL_n(𝔽_q)|=q^{n^2}(c_q+o(1))`$ with $`c_q=_{j=1}^{\mathrm{}}(1q^j)`$. Therefore,

$$\rho \text{Pr}[Mv\overline{S}\text{ when }\text{wt}(v)=R](c_q^1+o(1)).$$

Now, for a vector $`v`$ of weight $`R`$, define $`A_v`$ to be the event that $`MvS`$, and let $`I(v)`$ denote the set of indices at which $`v`$ is nonzero. Then $`\text{Pr}[Mv\overline{S}\text{ when }\text{wt}(v)=R]=\text{Pr}[_v\overline{A_v}]`$. The relation $`vw`$ iff $`I(v)I(w)\mathrm{}`$ clearly defines a superdependency graph on these events. Furthermore, any pair $`A_v`$ and $`A_w`$, $`vw`$, are independent, since, if we fix the $`i^{\text{th}}`$ columns of $`M`$ for $`iI(v)I(w)`$, then $`_{iI(v)I(w)}Me_i`$ and $`_{iI(v)I(w)}Me_i`$ are independent and uniformly distributed over $`𝔽_q^n`$. Therefore,

$`y(v,w)`$ $`=2\text{Pr}[A_v]\text{Pr}[A_w]{\displaystyle \underset{zv\text{ or }zw}{}}(1\text{Pr}[\overline{A_z}])^1`$
$`2\left({\displaystyle \frac{K}{\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R}}\right)^2\left(1{\displaystyle \frac{K}{\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R}}\right)^{2\left(\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R\left(\genfrac{}{}{0pt}{}{nR}{R}\right)(q1)^R\right)}`$
$`=2\left({\displaystyle \frac{K}{\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R}}\right)^2\left(1{\displaystyle \frac{K}{\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R}}\right)^{\left(\genfrac{}{}{0pt}{}{n}{R1}\right)(2R^2+o(1))(q1)^R}`$
$`2\left({\displaystyle \frac{K}{\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R}}\right)^2e^{K\left(\genfrac{}{}{0pt}{}{n}{R1}\right)(2R^2+o(1))/\left(\genfrac{}{}{0pt}{}{n}{R}\right)}`$
$`=2\left({\displaystyle \frac{K}{\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R}}\right)^2e^{K(2R^3+o(1))/n}.`$
Since there are $`\left(\genfrac{}{}{0pt}{}{n}{R}\right)\left(\left(\genfrac{}{}{0pt}{}{n}{R}\right)\left(\genfrac{}{}{0pt}{}{nR}{R}\right)\right)(q1)^{2R}/2=O(n^{2R1})`$ relations $`vw`$, the quantity $`_{vw}y(v,w)`$ tends to $`0`$ as $`n\mathrm{}`$ so long as $`K=o(\sqrt{n})`$. Therefore, Suen’s Inequality implies that

$`\text{Pr}\left[{\displaystyle \underset{\text{wt}(v)=R}{}}\overline{A_v}\right]`$ $`(c_q^1+o(1)){\displaystyle \underset{\text{wt}(v)=R}{}}\text{Pr}[\overline{A_v}]`$
$`=(c_q^1+o(1))\left(1{\displaystyle \frac{K}{\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R}}\right)^{\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R}`$
$`(c_q^1+o(1))e^K.`$
Taking an initial segment of a random $`\mathrm{\Lambda }(\alpha ,,𝐱)`$ and adding in all the “uncovered” codewords yields an $`(n,R,q)`$-de Bruijn covering code.

###### Theorem 2.

For each $`n`$, there exists an $`(n,R,q)`$-de Bruijn covering code of length $`(R+1+o(1))q^n\mathrm{log}n/(\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R)`$.

###### Proof.

Fix any generator $`\alpha 𝔽_{q^n}^\times `$. Choose the basis $`=\{b_i\}_{i=1}^n`$ and the vector $`𝐱𝔽_q^n\{0^n\}`$ randomly and uniformly. Then define $`\overline{\mathrm{\Lambda }}(K)`$ to be the string of the first $`q^nK/(\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R)+n`$ symbols of $`\mathrm{\Lambda }(\alpha ,,𝐱)`$ (which we will call $`\mathrm{\Lambda }_1(K)`$), followed by a concatenated list (which we will call $`\mathrm{\Lambda }_2(K)`$) of all strings in

$$𝔽_q^n\underset{c𝒞}{}b_R(c)$$

where $`𝒞`$ is the set of codewords appearing as $`n`$ consecutive symbols (without wrap-around) in $`\mathrm{\Lambda }_1(K)`$. Then the resulting expected length of the string is given by

$$\text{E}(|\mathrm{\Lambda }_1(K)|+|\mathrm{\Lambda }_2(K)|)=\frac{q^nK}{\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R}+n+nq^n\underset{v𝔽_q^n}{}\text{Pr}[b_R(v)𝒞=\mathrm{}]$$
(2)
Furthermore, the constructed string is an $`(n,R,q)`$-de Bruijn covering code. By the discussion preceding Theorem 4, $`\text{Pr}[b_R(v)𝒞=\mathrm{}]`$ is bounded above by

$$\text{Pr}\left[\{\left(\underset{j=0}{\overset{n1}{}}e_{j+1}𝐱^{}M_{\alpha ,}^j\right)^1w:\text{wt}(w)=R\}f_{}(v+\{\alpha ^j\}_{j=1}^K)=\mathrm{}\right].$$

The matrix in the left-hand term is uniformly distributed over all invertible matrices, by Lemma 6. Therefore, by Proposition 8,

$$\text{Pr}[b_R(v)𝒞=\mathrm{}]e^K(c_q^1+o(1)).$$

Plugging this and $`K=(R+1)\mathrm{log}n`$ into (2) yields

$$\text{E}(|\mathrm{\Lambda }_1(K)|+|\mathrm{\Lambda }_2(K)|)\frac{q^n\mathrm{log}n}{\left(\genfrac{}{}{0pt}{}{n}{R}\right)(q1)^R}(R+1+o(1)),$$

so a $`(n,R,q)`$-de Bruijn covering code of the desired length exists. ∎

## 4 A Spectral Perspective

In this section, we describe a “spectral” test to see whether a given string is a de Bruijn covering code, and apply it to a probabilistic construction. Define $`e_N(x)=e^{2\pi ix/N}`$, as is standard notation.

###### Proposition 3.

Let $`S=(S(0),\mathrm{},S(M1))`$ be a $`q`$-ary string, for any $`q>1`$. Then $`S`$ is a de Bruijn covering code of radius $`R`$ and dimension $`n`$ if and only if the quantity

$$\underset{\omega =0}{\overset{q^n1}{}}\underset{j=0}{\overset{M1}{}}\underset{v:\text{wt}(v)R}{}\underset{m=0}{\overset{q^n1}{}}e_{q^n}\left[m(\omega \underset{i=0}{\overset{n1}{}}(S(i+j)+v_imodq)q^i)\right]$$
(3)
is positive, where $`v`$ varies over the set of $`q`$-ary sequences $`(v_0,\mathrm{},v_{n1})`$ and the index of $`S`$ is written modulo $`M`$. Otherwise, this expression is zero.

###### Proof.

In what follows, all parameters vary over the ranges indicated in the statement above. Note that

$$\underset{m}{}e_{q^n}(m(\omega \omega ^{}))$$

is positive if $`\omega =\omega ^{}modq^n`$, and zero otherwise. If we represent a $`q`$-ary word as an integer base $`q`$, then the $`j^{\text{th}}`$ word appearing in $`S`$ is $`_iS(i+j)q^i`$, and, if $`\text{wt}(v)R`$, this quantity plus $`_kv_kq^k`$ (digits added independently modulo $`q`$) is the $`j^{\text{th}}`$ word with each symbol altered in at most $`R`$ coordinates. Therefore, the quantity

$$\underset{v}{}\underset{m}{}e_{q^n}(m(\omega \underset{i}{}(S(i+j)+v_imodq)q^i))$$

is positive if and only if the word $`S(i+j)`$ is at most a distance $`R`$ from the word which is $`\omega `$ written base $`q`$. Taking the sum over $`j`$ and then the product over $`\omega `$, we get that (3) is positive if and only if $`S`$ is an $`(n,R,q)`$-de Bruijn covering code, and is zero otherwise. ∎

Consider the expected value of the above expression when we take a randomly, uniformly chosen binary string $`S\{0,1\}^M`$. Clearly, an $`(n,R,2)`$-de Bruijn covering code of length $`M`$ exists if and only if this expected value is positive, since (3) is always nonnegative.

###### Theorem 4.

An $`(n,R,2)`$-de Bruijn covering code of length $`M`$ exists if and only if

$$\underset{\text{j},\text{v},\text{m}}{}e_{2^n}\left[\underset{\omega =0}{\overset{2^n1}{}}m_\omega (\omega (2^n1)/2)\right]\underset{l=0}{\overset{M1}{}}\mathrm{cos}\left(\pi \underset{i,\omega }{}m_\omega (12v_{\omega ,i})2^{in}\right)>0,$$

where $`i`$ and $`\omega `$ range over all pairs so that $`0in1`$, $`0\omega 2^n1`$, and $`i+j_\omega =lmodM`$, and the ranges of the other parameters are given by

$$\begin{array}{c}\text{j}\{0,\mathrm{},M1\}^{2^n}\\ \text{m}\{0,\mathrm{},2^n1\}^{2^n}\\ \text{v}\{v\{0,1\}^n:\text{wt}(v)R\}^{2^n}.\end{array}$$

###### Proof.

First, rewrite (3) by moving the product inside and collecting terms involving the same digits of $`S`$:

$$\underset{\text{j}}{}\underset{\text{v}}{}\underset{\text{m}}{}e_{2^n}\left[\underset{\omega =0}{\overset{2^n1}{}}m_\omega \omega \right]\underset{l=0}{\overset{M1}{}}e_{2^n}\left[\underset{i,\omega }{}m_\omega (S(l)+v_{\omega ,i}mod2)2^i\right].$$
(4)
If $`X`$ is a random variable with two equally probable values $`A`$ and $`B`$, then $`\text{E}[e_M(X)]=e_M((A+B)/2)\mathrm{cos}(\pi (AB)/M)`$. Taking the expected value of (4) therefore gives

$$\underset{\text{j},\text{v},\text{m}}{}e_{2^n}\left[\underset{\omega =0}{\overset{2^n1}{}}m_\omega \omega \right]\underset{l=0}{\overset{M1}{}}e_{2^n}\left[\underset{i,\omega }{}m_\omega 2^{i1}\right]\mathrm{cos}\left(\pi \underset{i,\omega }{}m_\omega (12v_{\omega ,i})2^{in}\right)$$

since the digits of $`S`$ are independent. We may simplify this expression to

$$\underset{\text{j},\text{v},\text{m}}{}e_{2^n}\left[\underset{\omega =0}{\overset{2^n1}{}}m_\omega (\omega (2^n1)/2)\right]\underset{l=0}{\overset{M1}{}}\mathrm{cos}\left(\pi \underset{i,\omega }{}m_\omega (12v_{\omega ,i})2^{in}\right).$$

Unfortunately, this result does not yield a practical means of calculating $`M(n,R,2)`$, due to the large number of terms. Furthermore, it is unlikely that much cancellation can be identified in this sum, given the NP-hardness of determining a code’s covering radius . It may be possible, however, to exploit approximation algorithms for vertex-coverings to find a much simpler sum which yields a reasonable bound.

We also offer the following, in the spirit of the above results.

###### Proposition 5.

Let $`S=(S(0),\mathrm{},S(M1))`$ be a $`q`$-ary string, for any $`q>1`$, and denote by $`X`$ the union of the radius $`R`$ balls about each codeword appearing as an $`n`$-string in $`S`$. Then the number of points of $`[q]^n`$ not covered by $`X`$ is at most

$$\underset{\omega =0}{\overset{q^n1}{}}\underset{k=0}{\overset{\mathrm{}}{}}\frac{1}{k!}\left(\underset{j=0}{\overset{M}{}}\underset{\text{wt}(v)R}{}\underset{m=0}{\overset{q^n1}{}}e_{q^n}\left[m(\omega \underset{i=0}{\overset{n1}{}}(S(i+j)+v_{t,i}modq)q^i)\right]\right)^k$$

where $`v`$ varies over the set of $`q`$-ary sequences $`(v_0,\mathrm{},v_{n1})`$ and the index of $`S`$ is written modulo $`M`$.

###### Proof.

As above, the quantity

$$T(\omega )=q^n\underset{j=0}{\overset{M}{}}\underset{\text{wt}(v)R}{}\underset{m=0}{\overset{q^n1}{}}e_{q^n}\left[m(\omega \underset{i=0}{\overset{n1}{}}(S(i+j)+v_{t,i}modq)q^i)\right]$$

counts the number of times that $`\omega `$ is covered. Therefore $`_\omega e^{q^nT(\omega )}`$ is at least the number of uncovered points. ∎

One might conjecture that a sufficiently long sequence $`S`$ whose Fourier coefficients $`\widehat{S}(k)`$ are small, for $`k0`$, covers all but a small fraction of Hamming space. To avoid trivial cases, we must restrict our attention to sequences with approximately the same number of each symbol. However, this statement is false even in the binary case, as illustrated by the following simple example.

Define $`S=(S(0),\mathrm{},S(M1))`$, $`M`$ even, by $`(S(2j),S(2j+1))=(0,1)`$ with probability $`1/2`$ and $`(1,0)`$ with probability $`1/2`$, each pair chosen independently. Clearly, $`S`$ has the same number of $`1`$’s as $`0`$’s. The $`k^{\text{th}}`$ Fourier coefficient, $`k0`$, has square magnitude

$$|\widehat{S}(k)|^2=\underset{u,v=0}{\overset{M1}{}}e_M(k(uv))S(u)S(v).$$

The values of $`S(u)`$ and $`S(v)`$ are independent if $`|uv|>1`$, so the expected value of the above expression is

$`\text{E}[|\widehat{S}(k)|^2]=`$ $`{\displaystyle \underset{u,v=0}{\overset{M1}{}}}e_M(k(uv))\text{E}[S(u)S(v)]`$
$`=`$ $`{\displaystyle \underset{u=0}{\overset{M1}{}}}{\displaystyle \frac{1}{2}}+{\displaystyle \underset{|uv|>1}{}}{\displaystyle \frac{e_M(k(uv))}{4}}+{\displaystyle \underset{|uv|=1}{}}e_M(k(uv))\text{E}[S(u)S(v)]`$
$``$ $`{\displaystyle \frac{M}{2}}+{\displaystyle \underset{u,v=0}{\overset{M1}{}}}{\displaystyle \frac{e_M(k(uv))}{4}}{\displaystyle \underset{|uv|1}{}}{\displaystyle \frac{e_M(k(uv))}{4}}+2M`$
$``$ $`{\displaystyle \frac{M}{2}}+\left|{\displaystyle \underset{u=0}{\overset{M1}{}}}{\displaystyle \frac{e_M(ku)}{2}}\right|^2+{\displaystyle \frac{3M}{4}}+2M={\displaystyle \frac{15M}{4}}.`$
Any $`n`$-word appearing in $`S`$ has weight either $`n/2`$ or $`n/2`$. Therefore, there exists a sequence $`S`$ of length $`M`$ with Fourier coefficients $`\widehat{S}(k)\sqrt{M}`$ so that, for any fixed $`R`$, the number of codewords at most a distance $`R`$ from the resulting code is an $`O(n^{1/2})`$ fraction of the total.

It would be interesting to know whether the characteristic function of quadratic residues mod $`p`$ are a (near?) de Bruijn covering code whenever $`p=\mathrm{\Omega }(2^n/n^R)`$. Other possibilities for random-like constructions include the image of $`[0,(p+1)/2]`$ under the map $`ss^k`$ with $`(k,p1)=1`$, and the image of $`[0,(p1)/2]`$ under the map $`s\tau ^s`$, for some primitive root $`\tau `$. Unfortunately, because of the above example, the Fourier coefficients of these sets (which are known to be small) tell us nothing about how well they cover Hamming space.

## 5 Numerical Bounds

It is of interest to know $`M(n,R,q)`$ for small values of its parameters – in particular, for $`q=2`$, i.e., the binary case. First, we collect a few simple observations.

1. $`M(n,R,q)M(n+k,Rl,q+m)`$ for any $`k,l,m0`$. If a de Bruijn covering code $`𝒞`$ exists for parameters $`(n+k,Rl,q+m)`$, then certainly decreasing the dimension, increasing the radius, or decreasing the number of symbols will leave $`𝒞`$ covering everything. (In the case of decreasing the number of symbols, we can replace all occurrences of the excluded symbols to “0”. It is easy to check that this operation can only decrease distances from $`n`$-strings to the code.)
2. $`M(n,0,q)=q^n`$, as noted in the introduction.
3. $`M(n,R,q)=1`$ if $`Rn`$, by taking the string “0”.
4. $`M(n,R,2)=2`$ if $`n/2R<n`$, by taking the string “01”. The two resulting codewords are complements in the $`n`$-cube, and therefore every string is within $`n/2`$ of one of them. Furthermore, it is clear that at least $`2`$ codewords are necessary.
5. $`M(n,R,q)K_q(n,R)`$, the smallest number of codewords in a $`q`$-ary covering code of dimension $`n`$ and radius $`R`$.
6. $`M(n,R,q)M`$ if $`\mathrm{min}\{|nmodM|,|(n)modM|\}n2R1`$, where $`|xmody|`$ means the least nonnegative representative of $`x`$ modulo $`y`$. Indeed, if a $`(n,R,q)`$-de Bruijn covering code $`S=(s_0,\mathrm{},s_M)`$ exists, then every string of $`n`$ consecutive symbols has weight

$$\frac{n}{M}\text{wt}(S)+\text{wt}(s_i,\mathrm{},s_{i+A1})$$

for some $`i`$, where the indices are taken modulo $`M`$ and $`A=|nmodM|`$. Similarly, each such string has weight

$$\left(\frac{n}{M}+1\right)\text{wt}(S)\text{wt}(s_i,\mathrm{},s_{i+B1})$$

for some $`i`$, where $`B=|(n)modM|`$. Therefore, any two codewords appearing in $`S`$ can differ by at most $`C=\mathrm{min}\{A,B\}`$ in weight. If $`Cn2R1`$, then either the string $`0^n`$ or the string $`1^n`$ is at least a distance $`R+1`$ from any codeword.
7. Every $`(n,R,2)`$-de Bruijn covering code has a run of $`n/(R+1)`$ consecutive $`0`$’s and a run of $`n/(R+1)`$ consecutive $`1`$’s. Suppose a code did not contain $`0^k`$ with $`k=n/(R+1)`$. Then every element of the code has weight at least $`n/kR+1`$, so the word $`0^n`$ is not covered, a contradiction. An identical argument applies to the case of a run of $`1`$’s.
8. If there exists an $`(n,R,q)`$-de Bruijn covering code of length $`M`$, then there exists one of length $`M+n+k1`$ for all $`k0`$. If $`S`$ is the shorter string, append a copy of the first $`(n1)`$ symbols and $`k`$ arbitrary $`q`$-ary symbols to the end.
9. If there exists an $`(n,R,q)`$-de Bruijn covering code of length $`M(n,R,q)`$ that somewhere contains the string $`a^{n1}`$, then there exists an $`(n,R,q)`$-de Bruijn covering code of all lengths longer than $`M(n,R,q)`$. We may simply insert more copies of $`a`$ into the string to generate longer ones.
10. There are at least $`M(n,R,q)`$ $`(n,R,q)`$-de Bruijn covering codes of length $`M(n,R,q)`$. Since $`M(n,R,q)`$ is minimal, no such string has period less than $`M(n,R,q)`$, since otherwise we could truncate after a single period and achieve a smaller de Briujn covering code with the same parameters. Therefore, all cyclic translations of any de Bruijn covering code – which are each themselves de Bruijn covering codes – are distinct.

Below, we include a table of the best known bounds on the sizes of binary de Bruijn covering codes with various parameters. A single number in an entry indicates that the exact value of $`M(n,R,2)`$ is known; two numbers indicate an upper and lower bound. Bounds were achieved using the observations above, the table in , as well as software that searched the string space randomly (for upper bounds), and one which searched it exhaustively (for lower bounds). A few hundred hours of computing time on a 1.8 GHz Intel-based PC were used to construct this table.

## 6 Remarks and Further Questions

Statement 8 in the previous section highlights a frustrating property of de Bruijn covering codes that stands in stark contrast to ordinary covering codes: it is possible for one to exist of length $`M`$ but for none to exist of length $`M+1`$. For example, a $`(10,4,2)`$ code exists of lengths $`4`$ (“1100”), $`6`$ (“011100”), $`8`$ (“00111100”), and $`12`$ (“000011111100”), but none of lengths $`5`$, $`7`$, $`9`$, $`10`$, or $`11`$ exist. However, by the above, a $`(10,4,2)`$ code of all lengths at least $`13`$ must exist. Therefore, in addition to finding the smallest possible de Bruijn covering code, we would like to know when de Bruijn covering codes with lengths between $`M(n,R,q)`$ and $`M(n,R,q)+n1`$ exist.

Another difference between de Bruijn covering codes and ordinary ones is that there is no easy way to use known efficient codes to build efficient codes for larger $`n`$, smaller $`R`$, or larger $`q`$. It would be desirable to define a “product” analogous to direct sums for ordinary covering codes. Unfortunately, interlacing, the obvious candidate for such a product, appears to be very inefficient. We offer a different, though related construction which allows us to increase $`q`$ when the desired number of symbols is a perfect power of the number of symbols in the original code.

###### Proposition 6.

If $`a^s=b`$ for any positive integers $`a`$, $`b`$, and $`s`$, then for all $`n,R>0`$,

$$M(n,R,b)s^2\frac{M(sn,R,a)+sn}{s}s.$$

###### Proof.

Let $`t=M(sn,R,a)`$ and $`m=s^2(t+sn)/ss`$, and let $`C=(c_0,\mathrm{},c_{t1})`$ be a minimum-length $`(sn,R,a)`$-de Bruijn covering code. We construct an $`(n,R,a^s)`$-de Bruijn covering code $`C^{}=(c_0^{},\mathrm{},c_{m1}^{})`$ of length $`m`$. Choose some bijection $`\sigma `$ between $`(/a)^s`$ and $`/a^s`$, and define

$$c_j^{}=\sigma (c_{|sjmod(m/s)|},\mathrm{},c_{|s(j+1)1mod(m/s)|})$$

with indices on the left hand side taken modulo $`m`$ and indices on the right hand side taken modulo $`t`$. Evidently, $`C^{}`$ is well defined, since $`s|m`$. Now, suppose $`X=(x_0,\mathrm{},x_{n1})`$ is an $`n`$-string over $`a^s`$ symbols. We claim that there is some codeword in the set of consecutive $`n`$-strings of $`C^{}`$ which is within $`R`$ symbols of $`x`$.

Indeed, let $`x_j^{}=\sigma ^1(x_j)`$ for $`0j<n`$ and define $`X^{}=x_0^{}\mathrm{}x_{sn1}^{}`$, a string of length $`sn`$. Then some string $`X^{\prime \prime }`$ which differs from $`X^{}`$ in at most $`R`$ symbols occurs somewhere in $`C`$, say, beginning at coordinate $`k`$. $`X^{\prime \prime }`$ must occur at least $`s`$ times in $`C^{}`$, at coordinates $`k+jm/s`$ for $`0j<s`$. (If $`X^{\prime \prime }`$ “wraps around” in $`C`$, the extra $`sn1`$ symbols at the end of each block of length $`m/s`$ guarantee $`X^{\prime \prime }`$ appears in $`C^{}`$.) Furthermore, since $`(m/s,s)=1`$, the numbers $`k+jm/s`$, $`0j<s`$, represent all residue classes modulo $`s`$, so there is some $`r`$ so that $`k+rm/s0mods`$. Then the string

$$\sigma ^1(c_{k+rm/s}^{},\mathrm{},c_{k+rm/s+s1}^{})\mathrm{}\sigma ^1(c_{k+rm/s+(n1)s}^{},\mathrm{},c_{k+rm/s+ns1}^{})$$

appears in $`C`$ and at most $`R`$ of its coordinates differ from those of $`X`$. ∎

The most obvious question arising from the subject of the present work is the issue of whether the bound stated in Theorem 1 is best possible, i.e., whether the $`\mathrm{log}`$ factor can be dropped or the result can be extended to $`q`$’s which are not prime powers. We also would like to explain why so many of the entries in Table 1 are even.


format: text

text:
# A dialog on quantum gravity Carlo Rovelli

## A dialog on quantum gravity <br>Carlo Rovelli

The debate between loop quantum gravity and string theory is sometime lively, and it is hard to present an impartial view on the issue. Leaving any attempt to impartiality aside, I report here, instead, a conversation on this issue, overheard in the cafeteria of a Major American University. The personae of the dialog are Professor Simp, a high energy physicist, and a graduate student, Sal. The Professor has heard that Sal has decided to work in loop gravity, and gently tries to talk her out. Here is what was heard.

Sal – Hi Prof.

Simp – Hi Sal. So, I hear you are interested in loops.

Sal – Yes indeed, have been reading.

Simp – And?

Sal – Like it.

Simp – Do you want to start doing loops?

Sal – Maybe.

Simp – You are not going to find a job …

Sal – Maybe. I prefer follow what fascinates me in science. Time to grow old later.

Simp – Hmm. And what fascinates you so much?

Sal – The merging of GR and QM. Understanding space and time, that stuff.

Simp – String theory merges GR and QM.

Sal – Yes, but the price is too high.

Simp – Too high?

Sal – Extra dimensions, supersymmetry, infinite fields …

Simp – This is not a price, is fascinating new physics.

Sal – For the moment, is not new physics, is just our speculations.

Simp – So is loop quantum gravity.

Sal – Yes of course, but loop gravity does the trick using only GR and QM, and this we know for good, without all the extra baggage.

Simp – Really does the trick? All works with loops?

Sal – No, much is missing. But much is missing in string theory as well.

Simp – Not so much. In string theory you can compute scattering amplitudes and cross sections. I think you can’t even do that in loop gravity.

Sal – True, but there are other things you can compute, which you can’t compute in string theory.

Simp – That is?

Sal – Spectra of areas and volume, for instance.

Simp – But you cannot measure that.

Sal – You can in principle…

Simp – Maybe in principle, but not in practice …

Sal – Nor you can measure, in practice, the cross sections predicted by string theory … But there is a big difference.

Simp – That is?

Sal – The prediction with loops are unique, well fixed. Maybe up to a parameter, but no more than that. If, or when, we are able to measure areas, say cross sections, with Planck scale precision, we will find the numbers predicted by loop gravity. Or not. And we will know the theory is right. Or wrong. This is good science. Isn’ it?

Simp – There are predictions from string theory as well.

Sal – Like?

Simp – Like large extra dimensions. Supersymmetry. Transitions that cannot happen in the standard model.

Sal – You mean that if we do not find the experimental consequences of large extra dimensions we conclude string theory is wrong?

Simp – Of course not, large extra dimensions exist only in very special models.

Sal – So, the experiments on extra dimensions cannot kill string theory?

Simp – No they cannot.

Sal – And if supersymmetry is not found at the scale we expect, we do not abandon string theory?

Simp – No we don’t. It will be at a higher scale.

Sal – So, which experiment could kill string theory, in principle?

Simp – Nothing I could think off. The theory is very strong.

Sal – Seems to me is very weak. A good scientific theory is a theory that can be falsified.

Simp – I am not a philosopher …

Sal – I mean, it is a theory that gives definite predictions. Not a theory that never tells us what we will see in the next experiment, and that can accommodate any outcome of any experiment. What’s the good of a theory that can accommodate anything and the contrary of anything?

Simp – You are exaggerating a bit …

Sal – Yes…but at least, is there a version of string theory that agrees with the reality as we see it?

Simp – Of course! There are Yang-Mills fields, quarks, the graviton! What do you mean?

Sal – I mean a version of the theory and its vacuum, a Calabi-Yau manifold, or some other way of breaking down the theory to 4d and getting precisely the standard model, with the masses and the particle content we see in the world, including the families?

Simp – I think that there are Calabi-Yau manifolds that give a physics quite similar to the standard model.

Sal – Okay, but is there one that give precisely the standard model physics in the regime we have tested it?

Simp – Hmm…No, I do not think so…At least not precisely …

Sal – So, so far string theory does not really agree with the world we see … requires a long list of very complicated things that we do not see, such as supersymmetry and extradimensions … and does not give any definite, univocal, prediction on future experiments … is this a serious theory …?

Simp – It is only because we are not able to truly compute with it.

Sal – Of course, but this is cheap, it can be said about any sufficiently complicated theory … why should I believe strings in particular?

Simp – Because it is the only theory we have for combining GR and QM. Because it gives a finite quantum theory, including gravity. Because it deals with what is missing in the standard model. Because many aspects of reality that have been confirmed from experiment follow from string theory: gravity, gauge theories, fermions…. Because the theory has only one free parameter instead of the 19 of the standard model. Because it brings everything together, it is the theory of everything. And because it is a very beautiful theory.

Sal – Prof, can we discuss all that during lunch?

Simp – Sure, if you then accept discussing loop gravity.

During this exchange Sal and Professor Simp were standing in line and getting food. At this point, they sit at a table. Sal has noted down a few words on a napkin. A few other students, curious of the exchange, sit nearby and listen.

Sal – I have noted your points for string theory. Let me start by saying that obviously string theory is an extremely remarkable theory, it is full of wonders and surprises, it touches so much mathematics, it clearly talks well with the physics we know. I have a tremendous respect for the people who have developed it, who are my heroes. But the issue I want to address is to which extent we can be sure, at present, that this is the correct theory for describing nature. If we are reasonably sure of that, there is no reason to study alternatives. If we are not, we better study alternatives. Especially given that alternatives exist. So, let me address your list of reasons to believe that string theory is physically correct. I start with the first: it is the only theory we have for combining GR and QM…

Simp – I take this point back for the moment. I forgot you are studying loops. There is of course loop theory as well. Let’s talk loops later.

Sal – Good. You say that the theory has only one parameter, instead of the 19 of the standard model. In general, we are interested in a theory with less parameters if this theory allows us to derive, to compute the old free parameters. Can we do that using string theory?

Simp – Not yet.

Sal – So, as far as the 19 parameters of the standard model are concerned, string theory has basically replaced an open problem with another open problem.

Simp – Yes, but there is a hope to solve it.

Sal – I have no doubts that if all the wishful thinking of the string theorists is realized, then string theory is a perfect theory, and we do not need loops. But also if all the wishful thinking of the loop people is realized, then loop theory is a perfect theory, and we do not need strings. Let’s not talk about hopes, let’s talk about achievements.

Simp – Then the 19 parameters of the standard model are not understood.

Sal – All right. There are other open problems of the standard model, besides being able to compute all the constants. Like understanding why there are three families. Does string theory solve that?

Simp – …no …

Sal – why the cosmological constant is small ?

Simp – …no …

Sal – giving a better account of symmetry breaking ?

Simp – …no …

Sal – so?

Simp – Well, the theory derives the full complexity of the standard model from an extremely simple picture …

Sal – Wait a minute. I agree the bosonic string is a simple physical picture. But the bosonic string is physically bad because of the tachyon and it definitely does not give the standard model. You have to go, say, to the heterotic string, with gauge groups, superfields… a different behavior of the two halves of the theory … I wouldn’t call this an extremely simple picture. Plus, you have to select a very specific and complicated internal space, by hand, so far, to get the standard model. In general, you have to get to the second volume of a book on string theory to just begin to be able to understand the definition of models that have a chance of being realistic … and with all that, we haven’t even found a way to derive the standard model with all its details…

Simp – You talk as if string theory was an extremely complicated machinery invented out of the blue for no reason. Its funny features, like extradimensions, supersymmetries and all that, were not put there just for fun. There has been a compelling logical evolution. It is remarkable that these complications have solved specific theoretical problems combining into the final theory…

Sal – Which problems? …

Simp – …it all started with the dual models and the Veneziano amplitude…

Sal – …the amplitude Gabriele Veneziano wrote down realizes the duality that was conjectured to hold in the strong interaction physical amplitudes between the $`s`$ channel and the $`t`$ channel…

Simp – You know your history.

Sal – And does the Veneziano formula describe correctly the cross sections that we observe?

Simp – No, it does not. The physical high energy behavior of the strong interactions cross sections is not the one predicted by this formula.

Sal – Therefore a good physicist concludes that Veneziano formula was a nice theoretical idea, but not one that Nature likes, and abandons it, to study something else … I suppose we have to believe Nature, not to believe our beautiful formulas when they disagree …

Simp – In fact, the Veneziano formula was abandoned for strong interactions, but so much was found out of it, it was understood it could emerge from a string theory and it was realized that it could be used in a much better way.

Sal – Wait a minute, this story gives a historical account of the birth of an idea. But it has nothing to do with providing reasons for believing that this idea is physically correct. If anything, it shows that it was a wrong idea to start with. The Veneziano amplitude and the Dolen-Horn-Schmid duality in strong interactions were motivated by the observation of the resonances with high spin, the rough proportionality between mass and spin… If I understand correctly, all this is today understood on the basis of QCD. Even the apparent “stringy” behavior can be understood from QCD; tubes of flux of the color lines of force behave like small strings in some approximation. Therefore it is reasonable that some sort of string theory gives an approximate account of the phenomenology. The correct physical conclusion is that string theory is an approximate description at some scale, not a fundamental theory.

Simp – This in fact was the conclusion. However, it turned out that the Veneziano formula opens a vast and beautiful theoretical world. So much came out of it. Strings are good description for other gauge theories, like N=4 Super-Yang-Mills, and it is probable that a string description will be found for large N QCD.

Sal – I am reading a book, written long ago, where I just found this phrase: *“…perchè i nostri discorsi hanno a essere sopra un mondo sensibile, e non sopra un mondo di carta.”* Roughly: *“…our arguments have to be about the world we experience, not about a world made of paper”.* None of those theories is connected to the world, as far as we know.

Simp – The theory naturally includes a graviton, and we do experience gravity, and the theory is finite at high energy.

Sal – But it is only consistent in 26 dimensions, unlikely the world we experience.

Simp – But this can be corrected by using Kaluza-Klein compactification.

Sal – And we get a theory with a tachyon, that we do not experience, and questions the consistency of the theory.

Simp – This can be corrected with supersymmetry.

Sal – and so on… You keep getting a theory that is either inconsistent or badly disagrees with reality, and you keep making it more and more complicated…

Simp – …until you get a theory that has a chance of being consistent and agreeing with nature …

Sal – Maybe, but the different ingredients of the theory are not solutions of problems of the standard model, or solutions of problems we have in understanding of the world: they are solutions to problems raised by other ingredients of the same theory. According to the Catholic doctrine there are two miracles happening in a Mass: the first miracle is that wine becomes truly blood. The second miracle is that the blood looks and smells like wine… it is just a miracle added to patch up the inconsistency created by the first …

Simp – Don’t be irreverent. The point is that, you continue until you finally get a theory that is consistent and agrees with nature.

Sal – …or until you get a theory where you cannot compute anything, you cannot reduce it down to 4d, you cannot get the Standard Model back … and it is sufficiently involved and unfathomable that you can’t anymore prove it wrong, and just declare that everything is in it, to be found by future generations… And if any problem arise –say the vacua that you have found so far are all unstable, as was found in a recent paper by Gary Horowitz and others – the theory is sufficiently complicated that you can always wishfully think that there is something else in it that can save the day …

Simp – It is not the fault of the theoretical physicist if the path of the natural evolution of the research has lead to a theory which is very complicated.

Sal – And if it *was* the fault of the theoretical physicist? I suppose when you say “the path of the natural evolution of the research” you mean the line that goes along Fermi theory, QED, $`SU(2)\times U(1)`$, QCD, the standard model, and then grand unified theories, the revival of Kaluza-Klein, supersymmetry, supergravity, … strings…

Simp – Yes.

Sal – But what if this “path of natural evolution” has taken a wrong turn at some point. Seems to me there is precise break along this path.

Simp – What do you mean?

Sal – Dirac predicted the positron, and it was found. Feynman and friends developed a calculation method for photon-electron interactions, and it works to devastating precision. Weinberg Glashow and Salam predicted the neutral currents and they were found, and the W and Z particles and Carlo Rubbia found them, precisely where predicted, just to name some …

Simp – So?

Sal – And then?

Simp – Then what?

Sal – Then the Veneziano formula predicted a very soft high energy behavior of the amplitudes, and nature was *not* like that. The grand unified theories predicted proton decay at some precise scale, and proton decay was *not* found where expected. Kaluza-Klein theory, revived, predicted the existence of a scalar field that was searched by Dicke, and *not* found. Supersymmetry predicted the supersymmetric particles and these were *not* found where repeatedly annunciated. Extra dimensions did *not* show up where recently suggested by string theory…

Simp – But the proton may take a bit longer to decay, the masses of the supersymmetric partners may be higher …

Sal – Of course, they “might”. Everything is possible. But the cut between the previous fantastic sequence of successful predictions *right on the mark*, and, on the other hand, the later series of unsuccesses is striking. Before, experimental particle physicists were always smiling and walking like heroes: looked like God was reading Phys Rev D and implementing all suggestions of the theorists. Nowadays, thanks god they are still busy figuring out aspects of the standard model, because all the new physics that theoretician have suggested wasn’t there …

Simp – Theory has always made wrong predictions.

Sal – Yes, but also right predictions, and those are missing, after the standard model.

Simp – It is because energies of new predicted physics are too high.

Sal – Not at all. There have been plenty of predictions that were well within reach. They just were wrong.

Simp – So, what do you make of this?

Sal – That perhaps Nature is telling us that our path of theoretical research has taken a wrong turn, at some point …

Simp – This is not a proof.

Sal – Of course. The fact is that we do not know. But it is, to say the least, a strong reason for exploring alternatives to what you called “the natural path of the evolution of high energy physics”. It is a strong reason for being suspicious of the idea that string theory has to be right just because this path got to it. One follows a path with confidence as long as indications are positive; why should we all keep following a path, altogether, when negative indications pile up?

Simp – Maybe … But what if supersymmetry is seen?

Sal – Then we’ll have another conversation. But I have heard so many announcements that supersymmetry is “on the verge of being seen”. I am told that famous theoreticians claimed that supersymmetry was certainly going to be found in a year or two, otherwise they’d change their mind. This was many years ago, and they haven’t changed their mind yet. I understand changing mind is hard, especially just because of experimental evidence… But do we believe nature or we believe our fancies? I remember myself one “very” famous theoretical physicist giving a major talk in front of a big audience of mathematicians and saying that his experimental friends had just told him that the first evidence for supersymmetry was showing up in the data…he gave it as a great announcement… everybody was thrilled… In the same talk, he also announced that what mathematicians will do in the coming millenium is to study string theory…

Simp – Sal, no sarcasm…

Sal – Alright, I apologize. Let me come to another point of yours. That strings bring everything together, it is a theory of everything.

Simp – You cannot deny that.

Sal – No, I don’t deny that. But I am not sure that running after the theory of everything is the right way to go.

Simp – Do you think that an attempt to merge separate theories is misled?

Sal – Not al all, this has been very effective historically. What I am disputing is the idea of the theory of everything.

Simp – It is the old dream of physics.

Sal – Yes, but it has never worked. And it might fail to work this time as well.

Simp – This time is different. We have theories that almost explain everything we see.

Sal – This time is not at all different than the other times. Physicists have repeatedly believed in the past that they had theories that explain “almost everything we see”. The feeling that we are “almost” at the theory of everything was there just before quantum theory, at the time of Maxwell, just after Newton …it has always been wrong …

Simp – I am not a historian. It may be right this time …

Sal – On the basis of which evidence?

Simp – String theory …

Sal – A theory, we agreed, that so far does *not* describe the world we live in, does *not* give any precise univocal prediction, and, I can add, whose general foundations are still completely *un*clear?

Simp – Wait a minute. The theory is not in such a bad shape. The perturbative theory allows us to compute all finite scattering amplitudes in the deep quantum gravitational regime.

Sal – Does it really ? Quantum gravitation regime is when center of mass energy is far above Planck.

Simp – And?

Sal – And this is where the perturbation expansion stops converging …

Simp – You mean the divergence of the perturbative series itself, not the infinities in the individual terms.

Sal – Yes.

Simp – But the series diverges in all quantum field theories.

Sal – Yes, but those are known to be approximations. You can rely on some other theory at higher energy. This is supposed to be the final theory … The fundamental theory does not allow us to compute at the Planck scale?

Simp – Okay, not the perturbative theory …but then there are the nonperturbative aspects of the theory … In some cases it is possible to give a non-perturbative prescription for the definition of amplitudes, such as matrix theory for 11d space or AdS/CFT for asymptotically AdS spacetimes.

Sal – Anything about *our* world?

Simp – No sarcasm, Sal. You cannot discount all the nonperturbative aspects of the theory.

Sal – You mean the dualities, the various maps between strong coupling and weak coupling, Joe Polchinski’s branes and all that …

Simp – yes, the theory is far more rich that we expected, it is fantastic how …

Sal – I know, I go to seminars and hear the exclamations …

Simp – So?

Sal – So what?

Simp – So you are not convinced by that?

Sal – What should I be convinced of?

Simp – That we are beginning to understand the non perturbative regime as well, and remarkable phenomena happen.

Sal – Are you saying that the non perturbative regime is understood? That we can routinely compute in the nonperturbative regime?

Simp – Far from that.

Sal – So, the theory does *not* allow us to compute finite scattering amplitudes in the deep quantum gravitational regime…Would you agree in saying that the theory is well understood perturbatively, where it does *not* look like the real world, and we have only glimpses on its nonperturbative regime, but not yet a clear relation with our world?

Simp – I guess I would.

Sal – Well, after having been developed for so many years by the smartest physicists on the planet, numbered by the hundreds … this sound quite a poor result to truly excite me …

Simp – Your taste … Remains the solid fact that the theory provides a finite perturbation expansion for quantum gravity.

Sal – Fair. And this is remarkable, I agree. But even on that I have doubts.

Simp – Doubts?

Sal – Is there a proof that the theory is finite at all orders?

Simp – Everybody says is finite.

Sal – Everybody says so. But does anybody know for sure?

Simp – There are many indications.

Sal – Many indications is different from knowing for sure. There were also indications that supergravity was finite at all orders, and famous physicists gave inspired talks that the final theory of everything was found. It turned out not to be finite, at three loops or something.

Simp – hmm…

Sal – Let me put it short: is there a paper, a book, a report, which shows that it is finite at all orders? I am not asking for something convincing a mathematician. Just something convincing a field theorist who is just a bit skeptical. In 1986 the book by Green, Schwarz and Witten said that finiteness to all order is a common belief among string theorists, but complete proofs had not appeared yet. Now is more than fifteen years later. Have they since?

Simp – There is a 1992 paper by Mandelstam …

Sal – I know that paper. It proves that the divergence that people were most worried about, the dilaton divergence, does not occur in superstrings; but there are other sources of divergence. The books by Kaky and Polchinski, written after that paper, write quite clearly that there is no proof…

Simp – I do not really know if a proof of finiteness at all orders exists …

Sal – I have tried to found out. Perturbative finiteness was never shown past two loops. Actually, it is not even known if there is an unambiguous prescription for writing superstring amplitudes past genus 2. It is not clear if there is any well defined theory there. I’ve not spoken to anyone who is optimistic about the probability of the general case, except people who tell me its been proved long ago in some obscure paper only they know about, but can’t recall the exact reference, and never send it after promising to.

Sal – Listen, you have studied a bit of strings: it is a beautiful and vast world.

Sal – Yes, but “…our arguments have to be about the world we experience, not about a world made of paper”.

Simp – It is not just a world made of paper. The theory predicts fermions, gauge fields, quantum theory, and especially it predicts gravity. In a world where gravity was not observed, a theoretician with string theory would have predicted the existence of gravity.

Sal – Prof, do you really believe this?

Simp – Well, maybe no.

Sal – In a world where gravity was not observed, a theoretician, having noticed that the Veneziano amplitude disagrees with reality would have just discarded it. The reason we all got interested in string theory is because there is gravity in it, without previous knowledge of gravity, string theory would not have been taken seriously. I can write a theory of the standard model plus a field called Pippo, where the Pippo field could not exist without the Standard model, and then claim: “look! my theory is great: if we didn’t know the standard model, my theory would have discovered it! therefore my theory is right! therefore the Pippo field exists”. It is obviously a nonsense. We develop only the theories that agree with what we know so far. It is silly then to be proud that they agree with what we have seen so far. It is as if Weinberg claimed that the $`SU(2)\times U(1)`$ theory “predicted electromagnetism”, and in a world where electromagnetism had not been observed, he would have predicted it. It is a nonsense. In a world without electromagnetism he would not have invented his theory. In fact, Weinberg and Salam and Glashow never claimed that about their theory. The remarkable prediction of their theory, which gave confidence in it, was the neutral currents and the W and Z particles… Making a big deal of the fact that there is gravity in string theory is the kind of argument that can be raised only out of the desperation that this theory is not able to predict anything new with certainty…

Simp – I guess many people would agree with this…

Sal – This leaves the last point: that string theory is the only known way of combining GR and QM. Which leads us to loops.

Simp – Enough strings?

Sal – Yes, your turn to attack …Attack is easier than defense, given that we do not have any experimentally proven theory yet …

Simp – Alright. I know little on loop gravity, so, correct me if I am wrong. But for what I hear, the theory has difficulties in recovering the low energy limit.

Sal – True. It might be doable, but it is not done. One can write states related to certain classical solutions, but there is not yet a way to recover low energy perturbation theory.

Simp – And there isn’t a single loop quantum gravity.

Sal – You mean the definition of the hamiltonian constraint admits many variants. True.

Simp – Alright, this is the incompleteness, and I suppose smart people like you think they may fix it …

Sal – Thanks for the “smart”, Prof. But you said no sarcasm…!

Simp – Alright! Let me come to the serious points. First, we know there is no way of combining GR and QM without altering GR or adding matter.

Sal – How do we know this?

Simp – Because GR is nonrenormalizable.

Sal – This does not mean anything. There are several examples of quantum field theories that are well defined nonperturbatively, and are nevertheless nonrenormalizable if we try a perturbation expansion.

Simp – But why should GR be like that? GR is like Fermi theory. Empirically successful but nonrenormalizable. Therefore we must change its high energy behavior, like we did with Fermi theory.

Sal – How can you be sure that GR is like Fermi theory? This is one possibility, of course, but there is another possibility: that GR is *not* like Fermi theory, and that the reason it is nonrenormalizable is a different one.

Simp – Which one?

Sal – That it is the weak field perturbation expansion that fails for GR.

Simp – Why should it?

Sal – Because the weak field perturbation expansion is based on Feynman integrals that sum over infinite momenta, namely over regions of arbitrary small volume.

Simp – So?

Sal – Simple dimensional arguments show that these regions are unphysical in quantum gravity. They literally do not exist. It make no sense to integrate over degrees of freedom far smaller than the Planck length. In fact, loop gravity strongly supports this possibility, because one of the results of the theory is that volume is discrete at the Planck length. There is literally no volume smaller than a Planck volume in the theory.

Simp – I suppose this is an hypothesis of the theory.

Sal – No, it is not an hypothesis, it is a result.

Simp – How can that be?

Sal – The volume is a function of the metric, namely of the gravitational field.

Simp – Okay.

Sal – And the gravitational field is quantized.

Simp – Okay.

Sal – Therefore the volume is a quantum variable.

Simp – I am following.

Sal – Therefore it may be quantized.

Simp – And how do we know if it is?

Sal – As usual in quantum theory: we compute the spectrum of the corresponding operator.

Simp – You mean like the energy of an harmonic oscillator?

Sal – Precisely.

Simp – And?

Sal – And the calculation shows that the spectrum is discrete and there is a minimal nonvanishing volume. Hence in the theory there can be no Feynman integral over arbitrarily small volumes.

Simp – I am a bit confused. If the discrete volume is a result and not an input, what is the physical spacetime on which the theory is defined?

Sal – There is none.

Simp – I do not understand.

Sal – It is a background independent formulation.

Simp – But how can a field theory “not be defined on a spacetime”.

Sal – This is precisely what happens in classical GR. In fact, this is background independence realized.

Simp – In GR things move on a spacetime. Fields and particles have a dynamics on a curved spacetime. Maybe curved, but always a spacetime.

Sal – Physics on a curved spacetime is not GR. GR is the dynamics of spacetime itself. So, quantum GR is the theory of a quantum spacetime, not a quantum theory on various spacetimes.

Simp – But how can we do physics without a spacetime? You will not have energy, momenta, positions …

Sal – Indeed.

Simp – We do not know how to do physics without these concepts.

Sal – General relativistic physics, theoretical and observational, does very well without. Energy, momenta and positions can only be defined in certain limits or relative to certain objects.

Simp – But this means changing all the basic tools of quantum field theory.

Sal – This is precisely what happens in loop quantum gravity.

Simp – Wait, all our experience in quantum field theory teaches us that these tools are essential. Quantum field is the most effective tool we have to understand the world. I am not ready to abandon it.

Sal – But GR teaches us that we should do so.

Simp – You take GR too seriously. GR is just an effective nonlinear lagrangian for describing the gravitational interaction. It is most presumably just a low energy lagrangian. I would be surprised if there are no high energy corrections to the Einstein Hilbert action.

Sal – I think there is a confusion here.

Simp – A confusion?

Sal – Yes, between the details of the Einstein-Hilbert action and the general lesson of GR, which is diffeomorphism invariance or background independence. When the loop people talk about taking GR seriously, or about the lesson of GR, they do not mean the specific form of the Einstein-Hilbert action. They mean the fact that the fundamental physical theory has to be background independent. This means that in the fundamental theory there isn’t a fixed background spacetime and fields on it. There are just many fields that construct the spacetime itself. This is the conceptual novelty of GR that the loop people want to merge with quantum field theory. Not the details of the Einstein Hilbert action.

Simp – But background independence is also what string theory people are trying to achieve.

Sal – Yes, the question is why trying to achieve this with all the gigantic apparatus of string theory –and nobody seems to be succeeding yet– when it seems to be possible with just conventional GR alone –and the loop people seem already to be succeeding…

Simp – There are many indications in string theory that the background independent theory exists. The various dualities connect different expansions, they are all aspects of the same theory …

Sal – But nobody knows the general background independent formulation of this hypothetical theory …

Simp – Yes indeed.

Sal – While in loop gravity the background independent formulation is known.

Simp – But in this funny way without spacetime, without energy, without momenta, without all the usual machinery.

Sal – Everybody says they want background independence, and then when they see it they are scared to death by how strange it is … Background independence is a big conceptual jump. You cannot get it for cheap, with conventional means.

Simp – You can define string theory nonperturbatively by means of a flat space theory defined on the boundary of spacetime.

Sal – Yes, Juan Maldacena has indicated the way. But his model does not describe our world, it is highly unrealistic…

Simp – …yes, but it indicates that there may be a possibility of defining a realistic background independent theory via a boundary theory.

Sal – Maybe, but I haven’t seen the realistic model yet. It might be certain bulk theories are related to certain boundary theories, perhaps because they have the same symmetries, or something; or maybe are related in some sectors, I do not know. But even if it was true that a certain background independent theory can be mapped on a flat space theory, can we say we have understood background independent physics? You can map a special relativistic theory over a theory with a preferred frame, and compute there. As far as you do that, you have not yet understood Lorentz invariant physics… We want to find the right way of thinking in the background independent regime, not just map ourselves out of it.

Simp – Of course, but this might be a useful first step.

Sal – Of course, very well. Far from me to deny that in string there is an active search for background independent physics, or hints and glimpses. What I am saying is that in loop gravity there is already background independence, fully realized in the basics of the theory.

Simp – I may concede this, but in exchange one cannot go down to low energy physics. If loop theory is correct, can you compute the cross section for graviton-graviton scattering? Using your finite minimal volume, can you fix all the constants in front of the terms that conventional perturbation theory leaves undetermined?

Sal – I think they are working on it, but I haven’t seen anything solid yet… I guess this is the weak point of the loops, right now …

Simp – Good. I agreed about so many weaknesses of string theory!

Sal – Fine …

Simp – So, suppose I believe your quantum theory of general relativity alone without matter. Then I am still very far from a realistic theory. There is matter in the world.

Sal – In loop gravity you can easily couple fermions and Yang Mills fields. In fact, you can even do a supersymmetric theory if you want, the point is that it is not required by consistency, it is not required by experience, so there is not much interest. There were a few papers indicating it is possible. So, you just couple the matter you see in the world to quantum GR.

Simp – And you have no explanation of why there is that particular form of matter, that particular coupling in the standard model.

Sal – No. But so far strings do not seem to be more successful at that either. Hoping that some nonperturbative physics that we do not yet understand will pick the right Calabi-Yau manifold out of a million is not so much better than honestly saying that we do not understand why $`SU(3)\times SU(2)\times U(1)`$. I think we are still very far from the end of physics! Which is good, for us young people… Who knows, we simply do not understand the deeper physical reason of the standard model. I find a more appealing explanation of the standard model in Alain Connes vision, which ties it to a simple underlying geometry, than in the string idea that it is the minimum of a potential we know nothing about.

Simp – I suppose when you add matter to loop gravity you loose finiteness because there you get the usual infinities back.

Sal – Not at all! In fact finiteness extends even to, say QCD coupled to gravity. For the very same reason: there is no small volume. You see, from the point of view of QCD, being coupled to gravity is very much like living on a Planck scale lattice, where the theory has no infinities.

Simp – So, what is precisely the status of these finiteness results?

Sal – There are two sorts of finiteness results, as far as I have understood. In the hamiltonian formulation of the theory, one proves that the operators that define the theory nonperturbatively do not develop divergences. In fact, the mathematical foundations of loop gravity are extremely solid. They have been developed to the level of rigor of mathematical physics.

Simp – I know. On the one hand, this has made the theory solid, but on the other hand, it has made the language harder to follow for a high energy physicist.

Sal – Then, there is also another formulation of the theory, called spinfoams, which is a Feynman-like perturbation expansion for computing amplitudes. At least for some euclidean versions of this, there are mathematical theorems that state that the expansion is finite.

Simp – Up to which order in perturbation expansion?

Sal – At any order.

Simp – You mean there is a perturbation expansion which has been truly proven to be finite al all orders?

Sal – Yes sir. Unlikely for strings.

Simp – So, why one cannot compute all scattering amplitudes, say between gravitons, out of this?

Sal – Because the expansion is defined in a certain basis, and one does not know yet how to write the Minkowski vacuum state and the graviton states in this basis…

Simp – I see … for a moment you almost convinced me to study loops … So, if the loop people are not yet able to describe gravitons, what sort of physics can they actually describe, besides providing this loopy picture of reality at the Planck scale?

Sal – Black holes, with their entropy, early cosmology…

Simp – Yes, I have heard there is an active “loop quantum cosmology”, even with claims that inflation could be driven by quantum gravity effects… But let me come to some serious objections. Is it true that the Hilbert space of the theory is nonseparable?

Sal – No, it is not true. At some stage it was not properly defined. There is now a proper definition where the Hilbert space is separable.

Simp – But the theory is based on loop states, which are created by holonomy operators …

Sal – yes

Simp – …and we know that in QCD these states are not good. They are nonnormalizable; the field operator is smeared only in one dimension, which is not enough. And if you try to take these states as orthogonal basis states, you get everything wrong. It is the very starting point of the loop representation that is wrong.

Sal – All you said is correct in QCD. But gravity is different. It is truly different.

Simp – Why?

Sal – Precisely because of diff-invariance. Or, if you want, because the volume is quantized. Physically, it is not that the loop states are concentrated on infinitely thin lines: it is as if they have a Planck size. What happens mathematically is that the localization of the loop on coordinate space is pure gauge. The physical degrees of freedom are not in the localization of the loop, but only in what remains after you factor away diffeomorphisms, namely they are in the way the loops intersect or link. In fact, the infinities are precisely washed away by diff-invariance.

Simp – I am not sure I understand this.

Sal – Well, you have to enter the math of the theory. But the point is that the loop states become good states in gravity. Let me put it in this way. On a lattice, loop states form a perfectly well defined basis, right?

Simp – Yes of course, it is the continuum limit that gives problems.

Sal – Well, in gravity is like being always on a Planck size lattice, because each loop state does not live on a background spacetime. It lives on the lattice formed by all the other loops.

Simp – Hmm. I vaguely see. Is the theory Lorentz invariant?

Sal – I have no idea. I suppose that it is just like in classical GR. Lorentz invariance is not broken if the state of the gravitational field happens to be Lorentz invariant, and is broken if it is not…

Simp – You are confusing the symmetry of a solution with the symmetry of the theory. Classical GR is Lorentz invariant.

Sal – No, it is not. The Lorentz group acts in the tangent space at each spacetime point, of course. But the theory is not Lorentz invariant in the sense you mean. If it were, we could Lorentz transform all solutions of the theory, right? …like we can Lorentz transform all solutions of Maxwell theory.

Simp – We can’t?

Sal – What do you get if you boost of a cosmological Friedmann solution?

Simp – Okay, you are right. But if we additionally assume that spacetime is asymptotically Minkowskian…

Sal – Then yes, of course, if you impose Lorentz invariant boundary conditions you introduce a Lorentz invariance into the theory. There will be the asymptotic Lorentz group acting…But I am not sure there are quantum states that are exactly asymptotic Minkowskian in the quantum theory. Perhaps there are, perhaps at the Planck scale the symmetry is spontaneously broken by the short scale structure. Like a given crystal breaks the rotational symmetry of the dynamical theory of its atoms. But I don’t really know…

Simp – But isn’t the existence of a minimal length obviously intrinsically incompatible with Lorentz invariance?

Sal – No, this is a misconception.

Simp – Why? If I slowly boost the minimal length, it smoothly becomes shorter…

Sal – No, this is quantum theory. It would be like saying that the existence of a minimal size of the z-component of the angular momentum breaks rotation invariance, because you can smoothly rotate it to zero. In quantum theory what changes smoothly is the probability of getting this or that eigenvalue, not the eigenvalues themselves. Same with minimal length, which appears as an eigenvalue. If you begin boosting something which is in a length eigenstate, you get a smoothly increasing nonvanishing probability of getting a different length eigenvalue, not a shorter eigenvalue.

Simp – Ah! Nice. So, does loop gravity predicts Lorentz violation or not?

Sal – I am not sure. I think so far it is like large extra dimensions for strings. Could be. Could not.

Simp – hmm… But if you have no Lorentz symmetry, you may have no hermitian hamiltonian. Is loop gravity unitary?

Sal – No, as far as I understand.

Simp – This is devastating.

Sal – Why?

Simp – Because unitarity is needed for consistency.

Sal – Why?

Simp – Because without unitarity probability is not conserved.

Sal – Conserved in what?

Simp – In time.

Sal – Which time?

Simp – What do you mean “which time?”. Time.

Sal – There isn’t a unique notion of time in GR.

Simp – There is no coordinate t?

Sal – There is, but any observable is invariant under change of t, therefore everything is constant in this t just by gauge invariance.

Simp – I am confused.

Sal – I know, it is always confusing…Nonperturbative GR is quite different from physics on Minkowski …

Simp – Do we really need to get in the conceptual complications of GR?

Sal – Well, if we are discussing the theory that is supposed to merge GR and QM …

Simp – String theory merges the two without these complications.

Sal – This is why I think that string theory does not really merge GR and QM.

Simp – But you agreed it does.

Sal – No, I agreed that strings provide a finite perturbation expansion for the quantum gravitational field and this expansion breaks down when things begin to become interesting: in the strong field regime.

Simp – So, why does string theory not merge GR and QM?

Sal – Precisely because GR tells us that there is no fixed background space with stuff over it. Strings are always about background spaces with stuff over them.

Simp – But the background derives simply from the split between the unperturbed and the perturbed configuration of the field, which we always do in quantum field theory.

Sal – We do so in perturbative theory. We do not do so if we define QCD as the limit of the lattice theory. And weak field perturbation theory might not work in gravity.

Simp – And what do you make of what is known about nonperturbative string theory?

Sal – What is known are relations between theories defined over different backgrounds. These are hints that the background independent theory might exist. But this is far from understanding the foundations of the background independent theory.

Simp – The fully background independent theory is an immense task, we are far from it.

Sal – Loop gravity does it.

Simp – And what do field and things stand on?

Sal – On top of each other, so to say.

Simp – It is not quite similar to the physics I know.

Sal – It is beautiful. You talked about the beauty of string theory. The emergence of spacetime as excited states, as loop and spinnetwork states, is extremely beautiful. It is quantum theory and general relativity truly talking to each other …

Simp – If background spacetime is missing, so is time?

Sal – Yes sir.

Simp – And if you do not want to impose asymptotic flatness you do not have asymptotic background time either?

Sal – Yes sir.

Simp – And if there is no background time, there cannot be unitary evolution, right?

Sal – Yes.

Simp – I am not sure I can digest a theory where there is no space and no time to start with, and without unitarity…

Sal – I suppose this is why there is so much resistance to loop gravity … Again, everybody searches background independence, but when you see it, it is sort of scary… Anyway, we can all believe what we like, until experiments will prove somebody right and somebody wrong, and for the moment no experiment is talking to us … Future will tell … But my point is that the absence of unitarity does *not* imply that the theory is inconsistent. Only that the notion of time is intertwined with dynamics. It is similar to the fact that there is no conserved energy in a closed universe …

Simp – Alright, I accept this. But we have been digressing… can we try to wrap up?

Sal – Alright. I suppose your conclusion is that loop gravity is (a) too different from usual QFT, (b) not completed and (c) not yet able to recover low energy physics…

Simp – And your conclusion is that string theory (a) does not describe the real world in which we live, (b) is not predictive because it can agree with any experimental outcome, (c) it requires an immense baggage of new phenomenology like supersymmetry, and extradimensions, which we do not see, and (d) it has not lead to a true conceptual merge of QM with the GR’s notions of space time…

Sal – Of course, they could both be wrong …

Simp – Or both right: loops might end up describing some aspects of quantum gravity and strings some other aspects…

Sal – Prof, maybe I was a bit carried away by the polemical verve, so let me be clear. I think that string theory is a wonderful theory. I have a tremendous admiration for the people that have been able to build it. Still, a theory can be awesome, and physically wrong. The history of science is full of beautiful ideas that turned out to be wrong. The awe for the math should not blind us. In spite of the tremendous mental power of the people working in it, in spite of the string revolutions and the excitement and the hype, years go by and the theory isn’t delivering physics. All the key problems remain wide open. The connection with reality becomes more and more remote. All physical predictions derived from the theory have been contradicted by the experiments. I don’t think that the old claim that string theory is such a successful quantum theory of gravity holds anymore. Today, if too many theoreticians do strings, there is the very concrete risk that all this tremendous mental power, the intelligence of a generation, is wasted following a beautiful but empty fantasy. There are alternatives, and these must be taken seriously. Loop gravity is pursued by a far smaller crowd; has problems as well, as you pointed out, but is succeeding in places where strings couldn’t get, and is closer to reality. And if you think at the quantum excitations bulding up physical space, you truly see quantum mechanics and general relativity talking to one another. And is beautiful. I have an immense respect for string theorists, but I think it is time to explore something else. Don’t you think, to say the least, that both theories are worthwhile exploring?

Simp –

The final words of Professor Simp were not heard. But he was seen smiling, and later heard referring to Sal as stubborn, but definitely smart. By the way, Sal is still looking for a job…

———–

Many thanks to Ted Newman, Gary Horowitz, Abhay Ashtekar, Daniele Oriti, Lee Smolin, Warren Siegel, Simone Speziale and Juan Maldacena for corrections and suggestions.