Introduction to Ideal Quilts

Year: 2011 Authors: Andrzej K. Brodzik

Core claim

Ideal quilts provide a geometrical, group-theoretic representation of ideal sequences and a bridge to abstraction in visual art.

Topics

ideal sequences, group theory, Zak space, abstraction, perfect polyphase sequences

Domains

group theory, correlation bounds, sequence design, finite permutations, modern art, abstract art, visual patterning, cultural design

Methods

coset decomposition, permutation construction, Zak space representation, comparative visual analysis

Media

diagrams, quilt images, finite chirp plots, printed figures

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2011: Mathematics, Music, Art, Architecture, Culture

Introduction to Ideal Quilts

Andrzej K. Brodzik The MITRE Corporation 202 Burlington Road Bedford, MA 01730 USA Email: abrodzik@mitre.org

Abstract

The mathematical construction of ideal quilts is outlined and a relationship of ideal quilts with certain ideas in modern arts centered on the grammar of abstraction is explored.

Introduction

Ideal quilts are two-dimensional representations of families of ideal sequences [1]. These ideal sequences are unique algebraic constructions satisfying certain group-theoretical properties [7]. The word ideal denotes a special property of a sequence that makes it as dissimilar to itself and to other sequences as possible. In that sense, an ideal sequence can be thought of as an elementary sequence, or as a sequence that contains an indivisible quantum of information [9], [17]. Mathematically, ideal sequences satisfy the so-called Sarwate bound, that is, they have zero out-of-phase autocorrelation and minimum cross-correlation side-lobes [15]. Construction of ideal sequences is, in general, a very difficult task. It is not known how many such sequences exist, however, it is conjectured that any such sequence can be represented abstractly by a sub-image of an ideal quilt [5]. Ideal sequences appear implicitly or explicitly in many application fields, including the design of radar, sonar and communication waveforms [10], [16].

Construction and Examples

The construction of families of ideal sequences, also referred to as perfect polyphase sequences, or PPS, can be described using the language of group theory [2]. The main stage of the construction is the coset decomposition of a certain permutation group. This permutation acts on a certain two-dimensional representation (Figure 2) of a prototype ideal sequence (Figure 1), known in engineering applications as finite chirp [5].

Identify the set of all perfect correlation sequences with the group of $(L-1)$-point permutations, $G_L$, where $L$ is a prime. The collection of PPS can then be associated with the right cosets of the permutation group generated by the multiplicative group of integers modulo $L$, $(\mathbb{Z}/L{)}^{\times }$. For example, consider the group $(\mathbb{Z}/5{)}^{\times }$ and choose 2 as the primitive root. Taking consecutive powers of 2 yields the permutation

$\pi$ is the generator of the cyclic group

$H_5=\{{\pi }^0,{\pi }^1,{\pi }^2,{\pi }^3\}=\{(1,2,3,4),(2,4,1,3),(4,3,2,1),(3,1,4,2)\},$ (2)

which is a subgroup of the group of permutations of the sequence $(1,2,3,4)$, $G_5$, under the operation of permutation composition. It follows that the right coset decomposition of $G_5$ can be expressed, for example, as

$G_5=H_5\cup \{H_5(3,4)\}\cup \{H_5(2,3)\}\cup \{H_5(2,3,4)\}\cup \{H_5(2,4,3)\}\cup \{H_5(2,4)\}.$ (3)

This decomposition can given directly, as a list,

[ \begin{array}[]{lll}(1,2,3,4),\ (2,4,1,3),\ (3,1,4,2),\ (4,3,2,1)\ (1,2,4,3),\ (2,4,3,1),\ (3,1,2,4),\ (4,3,1,2)\ (1,3,2,4),\ (2,1,4,3),\ (3,4,1,2),\ (4,2,3,1)\ (1,3,4,2),\ (2,1,3,4),\ (3,4,2,1),\ (4,2,1,3)\ (1,4,2,3),\ (2,3,4,1),\ (3,2,1,4),\ (4,1,3,2)\ (1,4,3,2),\ (2,3,1,4),\ (3,2,4,1),\ (4,1,2,3)\ \end{array} ] (4)

The array describes the second image in Figure 3. In general, $G_L$ has the decomposition

$G_L={\bigcup }_{g\in G_L}{H}_{L}g,$ (5)

where $H_L$ is the cyclic permutation group associated with $(\mathbb{Z}/L{)}^{\times }$.

The collection of PPS in (4) forms a partition of the set of all perfect auto correlation sequences. The first PSS in the partition is the set of the so-called generalized Frank sequences. The remaining PPS sets are formed by permutations of sequences in the first set. Other constructions can be obtained using different subgroups. The freedom of subgroup selection, together with close coupling of permutations and modulations in the broader time-frequency setting, avails a powerful new framework for the design of new ideal sequences. This framework, due to the special structure of the Zak space correlation, is inherently geometrical [5]. This advantage can be further enhanced by simultaneously operating on collections of sequences, known as ideal quilts [6].

Ideal quilts are $L(L-1)$ by $L(L-2)!$ images associated with entire coset decompositions, such as the coset decomposition in (5). These images are made up of permutations of the canonical $L$ by $L$ image of a diagonal line (Figure 2). The size of an ideal quilt increases very rapidly (Figure 3). For $L=3$ the quilt is 6 by 3. For $L=5$ the quilt is 20 by 30. For $L=7$ the quilt is 42 by 840. For $L=11$ the quilt is 110 by 3,991,680. To plot the last quilt at the resolution of the quilt of $L=7$ would take 19,008 pages.

Introduction to Ideal Quilts

Grammar of Abstraction

One of the main goals of both science and art is to reveal fundamental principles governing space and time. This task can sometimes be facilitated by juxtaposing structure and randomness, intention and accident [3]. Art that explores these relationships in a deep way does not function merely as a pleasing illustration of mathematical law, but forms an independent mode of an intellectual interrogation. It might be argued that this process is an integral component of all creative undertakings. Indeed, many examples of such explorations can be found not only in contemporary works of art, such as the paintings of Malevich, Kandinsky and Mondrian [3], [8], [11], [13], or some works of Duchamp [4], but also in the tribal designs of Berber veils, Javanese ikats, Asmat shield carvings, and aboriginal cave paintings [13]. One of the central questions that arise in these investigations is: what is the essential element of a visual representation? While the proposed solutions differ across cultural traditions and individual visions, it appears that in all cases a sense of some common fundamental grammar of abstraction emerges. Perhaps the most succinct description of this essential element was given by Kandinsky: All is made of lines and a line is a point in time [11]. One way to view these lines is by relating them to ideal sequences. These sequences can then be used in several ways: as measures of randomness [4] or complexity [8], [9], as manifestations of an ideal form [13], as patterns [14], as atoms [18], or - both metaphorically and literally - as prisms [12], [16]. Some of these viewpoints are further explored in [6].

References

[1] M. An, A. K. Brodzik and R. Tolimieri, Ideal sequence design in time-frequency space, applications to radar, sonar and communication systems, Applied and Numerical Harmonic Analysis, Birkhäuser, Boston, 2008.

[2] M. A. Armstrong, Groups and symmetry, Springer, New York, 1988.

[3] R. Arnheim, Art and entropy, University of California Press, Berkeley, 1974.

[4] J. C. Bailly, Duchamp, Palgrave MacMillan, New York, 1986.

[5] A. K. Brodzik, “Construction of sparse representations of perfect polyphase sequences in Zak space with applications in radar and communications”, EURASIP Journal on Advances in Signal Processing, Special Issue on Recent Advances in Theory and Methods for Nonstationary Signal Analysis, January 2011.

[6] A. K. Brodzik, Ideal quilts, in preparation.

[7] A. K. Brodzik and R. Tolimieri, “Bat chirps with good properties: Zak space construction of perfect polyphase sequences”, IEEE Transactions on Information Theory, Vol. 55, No. 4, April 2009, pp 1804-1814.

[8] J. Casti and A. Karlqvist (Eds), Art and complexity, Elsevier, Amsterdam, 2003.

[9] B. Edmonds, “Syntactic measures of complexity”, Doctoral Thesis, University of Manchester, Manchester, UK, 1999.

[10] S. W. Golomb and G. Gong, Signal design for good correlation, Cambridge University Press, 2005.

[11] W. Kandinsky, Point and line to plane, Dover, New York, 1979.

[12] R. Mähler, At the zero point of photography, Verlag Niggli and Fotostitung Schwiez, Zurich, 2006.

[13] K. Malevich, The non-objective world, Paul Theobald & Co, Chicago, 1959.

[14] G. Rickey, Constructivism: origins and evolution, George Braziller, New York, 1967.

[15] D. V. Sarwate, “Bound on crosscorrelation and autocorrelation of sequences”, IEEE Trans. Information Theory, Vol. 25, No. 6, pp 720-724, November 1979.

[16] M. R. Schroeder, Number theory in science and communication, Springer-Verlag, New York, 1986.

[17] S. B. Volchan, “What is a random sequence?”, Am. Math. Monthly, Vol. 109, pp. 46.63, 2002.

[18] L. Wittgenstein, Tractatus Logico-Philosophicus, Routledge, London, 2001.

Brodzik

Figure 1: Finite chirp, real and imaginary parts.

Figure 2: Zak space representation (magnitude) of a finite chirp.

Figure 3: Ideal quilts $L=3$ (left), $L=5$ (center), and $L=7$ (right). The quilt 7 contains corruptions induced by printer. These corruptions were left intentionally uncorrected to counter-balance symmetry of the image.