Date: Jan. 28 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: Victor S. Miller, Center for Communications Research, Princeton.
Title: Counting Matrices that are Squares
Abstract: On the math-fun mailing list (7 May 2013), Neil Sloane asked to calculate the number of n times n matrices with entries in {0,1} which are squares of other such matrices. In this paper we analyze the case that the arithmetic is in GF(2) We follow the dictum of Wilf (in the paper ``What is an answer?'') to derive a ``effective'' algorithm to count such matrices in much less time than it takes to enumerate them. The algorithm which we use involves the analysis of conjugacy classes of matrices. The restricted integer partitions which arise are counted by the coefficients of one of Ramanujan's mock Theta functions, which we found thanks to Sloane's OEIS (Online Encyclopedia of Integer Sequences).
Title: Cyclic permutations, shuffles, and quasi-symmetric functions
Abstract: Richard Stanley proved that the distribution of descent number over all the shuffles of two permutations depends only on the descent numbers of the permutations.
We present an explicit cyclic analogue of this result. The tools used for the proof include a new cyclic counterpart of Gessels quasi-symmetric functions, an unusual ring homomorphism, and a mysterious binomial identity with an interesting history.
Based on joint work with Ira Gessel, Vic Reiner, and Yuval Roichman.
Date: Feb. 11 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: Colin Defant, Princeton University
Title: Cumulants and Stack-Sorting
Abstract: Cumulant sequences are numerical sequences that play a fundamental role in noncommutative probability theory. West's stack-sorting map is a combinatorially-defined operator that acts on permutations. In this talk, we will discuss how cumulants and stack-sorting, two topics from very disparate worlds, are actually very closely related. This unexpected connection allows us to use tools from noncommutative probability theory to prove difficult, surprising, and (occasionally) weird facts about the stack-sorting map. We will explore several applications of this method.
Title: Game Complexity: Between Geography and Santorini
Abstract: Santorini, a board game designed by mathematician Gordon Hamilton, is a two-player game of perfect information (a partizan combinatorial game) with simple rules and great depth of strategy. The structure of Santorini suggests a number of possible generalizations and simplifications that can be studied. We are interested in the difficulty of finding winning strategies in this family of games. One of our variants of Santorini turns out to be equivalent to a classical game called Geography, which is known to be "hard." In this talk, we present some background on Santorini, Geography, and game complexity, and we discuss what we can say about certain variants of Santorini.
Based on joint work with Carson Geissler.
Date: Feb. 25 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker:
Aaron Robertson, Colgate University
Title: Data Mining and Ramsey Theory
Abstract: Ramsey theory concerns itself with the emergence of patterns in sufficiently large structures. Data miners search for patterns in extremely large data sets. This is a cautionary tale for data miners about making inferences from large data sets wherein we provide a framework for testing whether or not a correlation is spurious.
Date: March 4 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: David Nacin, William Patterson University.
Title: Padovan, Pascal, and Proofs without Words
Abstract: What happens when we attempt to construct the Fibonacci spiral with triangles instead of squares? We get a new sequence, the Padovan sequence, which answers its own collection of unique and beautiful counting problems. In this talk we will show how this construction defines this sequence and then rediscover the same sequence hiding again in other surprising places. We then prove several identities without using either words or numbers, by considering triangles composed of colored dots.
The Fibonacci sequence is connected to the golden ratio which arises from a simple question about rectangles and proportion. A slightly different natural question leads to a new ratio and yet another method for defining our sequence. We then observe the uses of this sequence and its ratio in architecture and discuss the history behind the patterns we've uncovered. We conclude with a counterexample to a conjecture about this sequence that leads us to a final construction involving copies of the Fibonacci sequence itself.
Date: March 11 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: Michael Kiessling, Rutgers University
Title: A Maple-assisted study of a Schroedinger-Newton, a.k.a. Schroedinger-Poisson, a.k.a. Choquard, a.k.a. Pekar, a.k.a. ... equation
Abstract: In several different contexts (mathematical) physicists have proposed a nonlinear system of PDEs which can be recast into a single Schroedinger equation with a Schroedinger potential that is the solution to a Poisson equation with the square of the solution of the Schroedinger equation as source term; as such it is known under a variety of names (see above). For instance, Roger Penrose proposed it in his theory of gravity-induced quantum-mechanical wave function collapse, but also down-to-earth condensed matter theories, by Pekar and later by Choquard, produce this equation without invoking gravity. Interestingly, the question of the asymptotic large-distance behavior has received several plausible but conflicting answers which cannot all be true simultaneously. Recently I managed to settle the issue of the leading order term --- partly rigorously, partly with the help of Maple. Subsequently Andrey Yudin from Moskow managed to tickle Maple to produce an intriguing formula for all the putative asymptotic correction terms to the leading order term which are of power law type. Numerically this formula seems pretty accurate, but it has yet to be proved; moreover, there are correction terms beyond all orders of powers, and a formula for these terms has yet to be found
Date: March 25 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker:
Alejandro Morales, UMass, Amherst, and William Shi, Northview highschool, Johns Creek, GA.
[starting Harvard, Fall 2021]
Title: Refinements and symmetries for volumes of flow polytopes
Abstract: Flow polytopes are an important class of polytopes in combinatorics whose lattice points and volumes have interesting properties and relations. The Chan-Robbins-Yuen (CRY) polytope is a flow polytope with normalized volume equal to the product of consecutive Catalan numbers. Zeilberger proved this by evaluating the Morris constant term identity, but no combinatorial proof is known. There is a refinement of this formula that splits the largest Catalan number into Narayana numbers, which Mészáros gave an interpretation as the volume of a collection of flow polytopes. We introduce a new refinement of the Morris identity with combinatorial interpretations both in terms of lattice points and volumes of flow polytopes. Our results generalize Mészáros's construction and a recent flow polytope interpretation of the Morris identity by Corteel-Kim-Mészáros. We prove the product formula of our refinement following the strategy of the Baldoni-Vergne proof of the Morris identity.
slides (w/o annotations) slides (w annotations)
Date: April 1 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: Doron Zeilberger, Rutgers University
Title: Proofs of the Riemann Hypothesis, the P ≠ NP conjecture, the Goldbach Cojecture, and the Irrationality of γ
Abstract: We present proofs of these conjectures, and time permitting, a few other ones.
[Joint work with Shalosh B. Ekhad]
Date: April 8 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker:
Eric Sundberg, Occidental College
Title: Pairing Strategies for Tic-Tac-Toe on the Boolean Hypercube
Abstract: We consider a tic-tac-toe-style game on the vertices of the n-dimensional Boolean hypercube
{0,1}n with k-dimensional subcubes as winning sets. We describe a pairing strategy which allows the second player to force
a draw when k = n/4 +1 in the case where n is a power of 4. Our results arose from significant experimentation using Mathematica.
(Based on joint work with Klay Kruczek and Ramin Naimi)
Date: April 15 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: Igor Pak, UCLA.
Title: What is a combinatorial interpretation
Abstract: The question in the title is deceptively simple, as the answers tend to be the number of certain trees, lattice paths, Young tableaux, and other friendly combinatorial objects. However, the question lies in the heart of connections between enumerative/algebraic combinatorics and computer science. I will survey what is known about the subject, and discuss some of my recent results.
Date: April 22 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: Toufik Mansour, University of Haifa
Title: On Stanley-Wilf limit of the pattern 1324
Abstract: We present an explicit formula for the generating function for the number of permutations of length $n$ that avoid
1324 in terms of generating functions for permutations that have a kernel shape of length m,
m ≥2. This allows us to write down a systematic procedure for finding a lower bound for approximating the Stanley-Wilf limit of the pattern 1324.
Joint work with Christian Nassau
Date: April 29 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: Victor S. Miller, IDA Center for Communications Research, Princeton
Title: Locality preserving hash functions, a partial order and tiles in binary space
Abstract: A "tile" in the space B^n of bit vectors of length n, is a subset S of B^n, such that there is another subset A of B^n so that every element of B^n can be written uniquely in the form a + s, where a in A and s in S. A particular class of tiles are the subsets of minimum weight elements in the cosets of a linear code over GF(2). In systematically investigating locality preserving hash functions, we generated the list of all possible tiles of cardinality <=64 satisfying a certain optimality condition. All but 10 of them turned out to be the sets of minimum weight elements described above. Attempts to prove the same for the remaining 10 remained elusive. Instead we found two computational criteria -- one using linear programming, and the other using combinatorial bin packing, which showed that remaining 10 could not be tiles.
[Joint with Don Coppersmith, Dan Gordon and Peter Ostapenko]
Date: May 6 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: Adi Ben Israel, Rutgers University (RUTCOR).
Title: Data analysis in high-dimensional spaces
Abstract:
1. The unreliability of the Euclidean distance in high-dimension, making a proximity query meaningless and unstable because there is poor discrimination between the nearest and furthest neighbor [3], see also [4].
2. The uniform probability distribution on the n-dimensional unit sphere S_n, and some non-intuitive results for large n. For example, if x is any point in S_n, taken as the "north pole", then most of the area of S_n is concentrated in the "equator".
3. The advantage of the ℓ1-distance, which is less sensitive to high dimensionality, and has been shown to "provide the best discrimination in high-dimensional data spaces," [1, p. 427].
4. Clustering high-dimensional data using the ℓ1 distance, [2].
References
[1] C.C. Aggarwal et al, On the surprising behavior of distance metrics in high dimensional space, Lecture Notes in Computer Science, vol 1973(2001), Springer, https://doi.org/10.1007/3-540-44503-X_27
[2] T. Asamov and A. Ben-Israel, A probabilistic ℓ1 method for clustering high-dimensional data, Probability in the Engineering and Informational Sciences, 2021, 1-16
[3] K. Beyer et al, When is "nearest neighbor" meaningful?, Lecture Notes in Computer Science, vol 1540(1999), Springer, https://doi.org/10.1007/3-540-49257-7_15
[4] J.M. Hammersley, The distribution of distance in a hypersphere, The Annals of Mathematical Statistics 21(1950), 447-452.
Title: Lovely New Problems From the Past Months
Abstract: Tired of the sequence [Covid, drought, fires, floods, war, repeat]? Then come and hear about the astonishing Inventory Sequence 0; 1, 1, 0; 2, 2, 2, 0; ...; a new counting problem based on the complete graph; the Stepping Stones puzzle; Problem of the Week 1321; the Ennesrem primes; Gerrymandering; Vicious Watermelons; and other highlights from the past few months of the OEIS. tbd
Title: Difference Ring Algorithms for Symbolic Summation and Challenging Applications
Abstract: A major breakthrough in symbolic summation was Doron Zeilberger's creative telescoping method to compute linear recurrences of definite hypergeometric sums. In this talk I will illustrate the algorithmic framework in the setting of difference rings in which one can extend Z's method for summands that are built by indefinite nested sums and products. In combination with a sophisticated recurrence solver one obtains a rather general machinery to simplify big classes of definite multi-sums to expressions in terms of indefinite nested sums and products. The underlying difference ring algorithms implemented in the summation package Sigma will be illustrated by non-trivial applications coming, e.g., from combinatorics and particle physics.
Title: Coloring subsets with r-wise intersecting color classes
Abstract: What is the minimum number of colors required in a coloring of all k-subsets of an n-set so that every color class is r-wise intersecting? We suggest a conjectured answer for all r, k and n, note that for r=2 this is Kneser's conjecture proved by Lovasz, and prove the conjecture for any r which is either a prime or a power of 2.
Title: An Experimental (yet fully rigorous!) Study of a certain "Measure Of Disarray" that 12-year Noga Alon Proved was always Even
Abstract: In a beautiful new "cofee table book", "Do not Erase", by the very talented artistic photographer Jessica Wynne, there are pictures of more than one hundred blackboards by a very diverse set of mathematicians. One of them is Noga Alon's blackboard. Each blackboard photo is accompanied by a short essay by the creator of the blackboard, where they often describe how they decided to become mathematicians. According to Noga Alon, the "epiphany" occurred when he was 12 years old, when he settled a heated argument in a "Eurovision watching party" that his parents threw, where he conclusively proved that a certain "measure of disarray" must always be even, in particular causing one of the guests, "a grown-up engineer", to concede that he was wrong in claiming that it was a coincidence that the scores turned out to be all even. According to Noga, the fact that a mere 12-year-old can win an argument against a grown-up (especially one who is an engineer) shows the objectivity of mathematical truth, and reinforced his decision to become a mathematician.
While I do agree that mathematical knowledge is more objective than most other kinds, it is not as objective as it seems.
But the point of the present talk is to investigate, in a purely empirical (yet fully rigorous!) way, that same measure of disarray,
that turned out to be called "Spearman's footrule", going far beyond just proving that it is always even,
considerably extending a 1977 paper by Persi Diaconis and Ron Graham, debunking yet-another myth:
that mathematics is always deductive.
Joint work with Shalosh B. Ekhad.
paper (instead of slides)
Date: Oct. 7, 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: Yochay Jerby, Holon Institute of Technology, Israel
Title: A dynamic approach for the zeros of the Riemann zeta function - Collision and repulsion
Abstract: he Riemann hypothesis is a question regarding the solutions of the transcendental equation ζ(s)=0, that is the zeros of the Riemann zeta function. The starting point of our talk is a remarkable connection between the zeros of zeta and the solutions of the much simpler equation χ(s)+1=0, whose non-trivial solutions could be completely described in closed form and all lie on the critical line. We will explain that the two equations are related by a sequence of functions ζN(s) called $N$-th sections of zeta. For N=1 one has ζ1(s)=1/2(1+χ(s)) while for N=[Im(s)/2] the section ζN(s) is approximately ζ(s), up to a small error. Studying the dynamical change of the zeros of ζN(s) with respect to N we will show that zeros can go off the critical line only if a process of collision occurs between two consecutive zeros at a certain stage. We will also suggest a method of re-arranging the dynamics so that collisions could be avoided altogether, that is, in a way expected to keep the zeros on the critical line for any N, including the final stage where they essentially coincide with the zeros of zeta. If time permits we will also discuss how the suggested viewpoint relates to various classical topics such as: Gram's law, the Davenport-Heilbronn function and the Montgomery pair correlation conjecture.
Title: Moments of permutation statistics and central limit theorems
Abstract: We show that if a permutation statistic can be written as a linear combination of bivincular patterns, then its moments can be expressed as a linear combination of factorials with constant coefficients. This generalizes a result of Zeilberger. We use an approach of Chern, Diaconis, Kane and Rhoades, previously applied on set partitions and matchings. In addition, we give a new proof of the central limit theorem (CLT) for the number of occurrences of classical patterns which uses a lemma of Burstein and Hasto. We give a simple interpretation of this lemma and an analogous lemma that would imply the CLT for the number of occurrences of any vincular pattern. Furthermore, we obtain explicit formulas for the moments of the descents and the minimal descents statistics. The latter is used to give a new direct proof of the fact that we do not necessarily have asymptotic normality of the number of pattern occurrences in the case of bivincular patterns tbd
Date: Oct. 21 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker: Orli Herscovici, Georgia Tech
Title: Combinatorics behind the degenerate Eulerian numbers
Abstract: Works of Carlitz gave an inspiration to many researchers to develop different generalizations of the Eulerian polynomials and numbers. Many of those generalizations have a pure analytical character. It is known that the classical Eulerian numbers and some of their generalizations are connected to combinatorial statistics on permutations. However, the degenerate Eulerian numbers had no combinatorial interpretation since their introduction by Carlitz in 1979. In this talk we consider a combinatorial model that generalizes the standard definition of permutations and show its relation to the degenerate Eulerian numbers.
Title: Accelerating hypergeometric indefinite summation
Abstract: One well-known longstanding problem with Gosper’s algorithm is that its running time depends at least linearly on the dispersion of the rational certificate of the summand, and this last can be exponentially large in the bit size of the summand. This makes summation problems for hypergeometric terms with large dispersion values effectively intractable. We show that for summable terms this dependency is not essential (can be removed). The structure of polynomial solutions to the Gospe key equation is analyzed. A method for rapid extractionsof simple high-degree factors of the solution is given. Resulting modified Gosper's algorithm is presented. This result is based on very simple and well-known facts, properties, and lazy evaluation rules of factorial polynomials. Experimental Maple implementation confirms practical acceleration in computing of indefinite sums and rational normal forms of hypergeometric terms.
Date: Nov. 4 , 2021, 5:00pm (Eastern Time)
Zoom Link [password: The 20th Catalan number, alias (40)!/(20!*21!), alias 6564120420 ]
Speaker:
Eric Rowland, Hofstra University
Title: Lucas congruences modulo p2
Abstract: In the 1870s, Lucas obtained a beautiful formula for binomial coefficients modulo p. Namely, Binomial[n, m] is congruent modulo p to the product of the binomial coefficients whose arguments are the base-p digits of n and m, taken pairwise. Variations and generalizations of this formula have been actively investigated since. In particular, for which n and m does Lucas' congruence hold not just modulo p but modulo p2? The answer is related to some hidden rotational symmetry in Pascal's triangle. A similar result holds for the Apery numbers, which Gessel showed satisfy a Lucas congruence in 1982
Title: Reflecting (on) the modulo 9 Kanade--Russell (conjectural) identities
Abstract: We examine complexity and versatility of five modulo 9 Kanade--Russell identities through their finite (aka polynomial) versions and images under the q -> 1/q reflection. This is a joint work with Wadim Zudilin.
Title: Counting Baxter Matrices
Abstract: Don Knuth recently introduced the notion of a Baxter matrix, generalizing Baxter permutations to 0-1 matrices. We will explain the definition by drawing some pinwheels on matrices, and show how to count them using finite state automata. Time permitting, we will prove that the number of 1's in a m by n Baxter matrix is less than m+n
Title: Sycamore and other quantum supremacy experiments
Abstract: The notable claim of quantum supremacy presented by Google's team in 2019 consists of demonstrating the ability of a quantum circuit to generate, albeit with considerable noise, bitstrings from a distribution that is considered hard to simulate on classical computers. Google's team estimated that the task performed by their quantum circuit would take 10,000 years on a classical supercomputer. In 2020 a team from the University of Science and Technology of China (USTC) claimed that the sampling task computed by their quantum computer, which differs from Google's, would take 2.5 billion years to perform on a classical supercomputer! In the lecture I will discuss three aspects of these claims.
A) The quality of the statistical tools and methods
B) The strength of the claims from computational complexity
C) The quality of the data
Title: Experimental Complexity Theory?
Abstract: Complexity theory is generally a two-handed piece between the upper bound O(f(n)) algorithm designers and the lower bound Ω(f(n)) example builders. If they agree, we're in Θ(f(n)) paradise. Implicit in this is "worst case''. Only rarely does "average case'' complexity get mentioned, not least because even defining "average case'' is hard. What the user of an algorithm is really interested in, of course, is "complexity on my problems''. Failing this, we could at least ask for "complexity on typical problems'', which raises "what is typical''. This is normally answered by having a collection of typical problems, something many fields (e.g. my own computer algebra) are pretty poor at. I will contrast this with the situation in SAT-solving, and finish with some ideas for the future.