Mathematics

In this talk, I will give a survey of recent work I have done—some published, some unpublished—on the historical, mathematical, and philosophical problems related to the assignment of "sizes" to infinite sets. I will focus in particular on infinite sets of natural numbers. The historical part of the presentation will take its start from Greek and Arabic contributions to the possibility of measuring infinite sets according to size and sketch some developments spanning the period between Galileo and Cantor. In the systematic part of the talk, I will discuss recent theories of numerosities that preserve the part-whole principle in the assignment of sizes to infinite sets of natural numbers and show how the historical and mathematical considerations yield benefits in the philosophy of mathematics. In particular, I will discuss (1) an argument by Gödel claiming that in extending counting from the finite to the infinite, the Cantorian solution is inevitable; and (2) consequences for neo-logicism.

Paolo Mancosu is the Willis S. and Marion Slusser Professor of Philosophy at the University of California, Berkeley. He has made significant contributions to the history and philosophy of mathematics and logic, especially the philosophy of mathematical practice, mathematical explanation, the history of 20th century logic, and neo-logicism. His most recent book, Abstraction and Infinity (Oxford Unversity Press, 2017), concerns the use of abstraction principles in the philosophy of mathematics. He previous books include Philosophy of Mathematics and Mathematical Practice in the Seventeenth Century (Oxford University Press, 1996), From Brouwer to Hilbert. The Debate on the Foundations of Mathematics in the 1920s (Oxford University Press, 1998), The Philosophy of Mathematical Practice (Oxford University Press, 2008), The Adventure of Reason. Interplay between Philosophy of Mathematics and Mathematical Logic: 1900–1940 (Oxford University Press, 2010), and Inside the Zhivago Storm. The Editorial Adventures of Pasternak’s Masterpiece (Feltrinelli, 2013).

A symmetric key cryptosystem is one in which the same secret key is used for both encryption and decryption. An encryption function in a block symmetric key cryptosystem is a function of both the key and a block of n bits of data, and the result would generally be n bits long. The bits can be considered to be values in GF(2), and these functions are called Boolean functions. Such an encryption function must be highly nonlinear, or the system can be broken.

One measure of the nonlinearity of a Boolean function is its multiplicative complexity, which is the number of modulo 2 multiplications (ANDs) needed to compute the function, if the only operations allowed are multiplication and addition of two values modulo 2 (AND and XOR) and adding 1 modulo 2 to a value (NOT). This talk will be a survey of some results concerning multiplicative complexity, including a comparison to some other measures of nonlinearity. Multiplicative complexity turns out to be interesting in a another way in settings such homomorphic encryption and multi-party cryptographic protocols, where it can be important that the functions being computed have low multiplicative complexity.

The number of inversions of a permutation is an important statistic that arises in many contexts, including as the minimum number of simple transpositions needed to express the permutation and, equivalently, as the rank function for weak Bruhat order on the symmetric group. In this talk, I’ll describe an analogous statistic on the reduced expressions for a given permutation that turns the Coxeter graph for a permutation into a ranked poset with unique maximal element. This statistic simplifies greatly when shifting our paradigm from reduced expressions to balanced tableaux, and I’ll use this simplification to give an elementary proof computing the diameter of the Coxeter graph for the long permutation. This talk is elementary and assumes no background other than passing familiarity with the symmetric group.

Azumaya algebras over a commutative ring R are generalizations of central simple algebras over a field k, and both are "twisted matrix algebras". In this, they bear the same relationship to a noncommutative ring of matrices Mat_n(k) that a vector bundles (or projective modules) bear to vector spaces. That is, they are bundles of algebras. In this talk, I will show that thinking about Azumaya algebras from the algebraic-topological point of view, as bundles of algebras, is fruitful, both in producing examples of algebras with interesting properties, and in proving certain results about such algebras that are difficult to prove by direct, algebraic methods.