DIMACS Conference on Challenges of Identifying Integer Sequences

October 9 - 10, 2014
DIMACS Center, CoRE Building, Rutgers University

Organizers:
Susanna Cuyler, The OEIS Foundation, susanna.cuyler (at) gmail.com
Eugene Fiorini, DIMACS, gfiorini (at) dimacs.rutgers.edu
Charles Greathouse, Case Western Reserve University, charles.greathouse (at) case.edu
Brian Nakamura, CCICADA, bnaka (at) dimacs.rutgers.edu
Lara Pudwell, Valparaiso University, Lara (dot) Pudwell (at) valpo (dot) edu
Vinay A. Vaishampayan, DIMACS, vavaishampayan at icloud.com
Doron Zeilberger, Rutgers University, zeilberg (at) math.rutgers.edu

Abstracts:

Jörg Arndt, Georg Simon Ohm Technische Hochschule Nuremberg

Title: There be dragons. Thousands!

About a dozen or so plane-filling curves, like the Hilbert curve, the Peano curve, the paperfolding (Harter-Heighway) dragon, the terdragon, and a few others, feature in about every publication on this subject. Can we give all of these curves? The answer is "yes", at least for a seemingly restrictive class of such curves. The sheer amount of curves found and their beauty will show the world has been waiting for this computation far too long! The Cretaceous-Paleogene extinction event is thereby successfully reversed.


Sara Billey, University of Washington, and Bridget Tenner, DePaul University

Title: Beyond the OEIS: Fingerprint databases for theorems

Suppose that M is a mathematician, and that M has just proved theorem T. How is M to know if her result is truly new, or if T (or perhaps some equivalent reformulation of T) already exists in the literature? In general, this question is hard to answer, and mistakes do occur. We will discuss several existing databases of theorems that encode results using small, language-free, searchable "fingerprints." We will also address the problem of how to canonically fingerprint other types of theorems and formulas throughout mathematics.


John Conway, Princeton University

Title: On Unsettleable Sequences

It has long been known that there are arithmetic statements that are true but not provable, but it is usually thought that they must necessarily be complicated. In this talk, I shall argue that these wild beasts may be just around the corner.


Russ Cox, Google

Title: Two Computation-Heavy Sequences

I am most intrigued by sequences with simple definitions masking high computational complexity. These often require significant structural or algorithmic insights to compute even a few terms. The talk examines two such sequences, involving the most complex AND-OR formulas over n-input Boolean functions (A056287) and the least complex automata recognizing a subsequence of the integers 1..n (A129403).


Edinah Gnang, Purdue University

Title: Counting Arithmetic Formulas

An arithmetic formula is an expression involving only the constant 1, and the binary operations of addition and multiplication, with multiplication by 1 not allowed. We obtain an asymptotic formula for the number of arithmetic formulas evaluating to n as n goes to infinity, solving a conjecture of E. K. Gnang and D. Zeilberger.


Jeff Lagarias, University of Michigan

Title: Products of binomial coefficients and Farey fractions

We study products of binomial coefficients, especially the product of the binomial coefficients in the n-th row of Pascal's triangle. We study their growth rate and prime divisibility.

We relate these to products of Farey fractions.


Douglas Hofstadter, Indiana University

Title: Analogies and Sequences: Intertwined Patterns of Integers and Patterns of Thought Processes

As a math-loving teen-ager, I got swept up into an intense and almost indescribably intoxicating binge of mathematical exploration, all of which was centered on the discovery (or invention?) of integer sequences. The very first discovery in this binge came out of an empirical exploration of the way in which triangular numbers intermingle with squares, and the discovery of the strange hidden order in the sequence that reflected their intermingling was extremely unexpected and exciting to me.

This huge burst of joy instantly gave rise to the desire to repeat the experience, which meant to recreate essentially the same phenomenon again, but in a new “place”, which meant to generalize outwards, and I carried out this generalization by exploring all sorts of “nearby” analogues, where the words “place” and “nearby” of course suggest (at least to mathematically inclined folk!) some kind of metaphorical, but perhaps objective, space of ideas, and in it, some kind of metaphorical metric.

Over the next few years, analogies and sequences came to me in wondrous flurries, giving rise to all sorts of discoveries, some very rich and inspirational to me, some of course less so, but in any case, these coevolving discoveries constantly pushed the envelope of richly-interconnected ideas outwards, revealing new and unsuspected caverns in this mysterious idea-space that I had stumbled upon. Some of my explorations gave rise to patterns that I could fully understand and prove, whereas others gave rise to mysterious, chaotic behaviors that were far too deep for me to fathom, let alone prove. After a while, I started hitting up against the limits of my own imagination, and thus, sadly, I gradually ran out of steam, but the several-year voyage had been incredible one of the greatest voyages in my life.

The talk will thus be all about the very human, intuition-driven, analogy-permeated nature of mathematical discovery, invention, and exploration not at the immensely abstract level of great mathematicians, to be sure but hopefully, the essence of the mental processes mediating the modest meanderings of a middling, minor mathematician is more or less the same as that of those that mediate the marvelous and majestic masterstrokes of a major, mature mathematician.


Lara Pudwell, Valparaiso University

Title: OEIS meets UGR

OEIS is already an influential resource for researchers in a variety of fields, but it takes on additional significance for students involved in undergraduate research (UGR). UGR students are often limited by time (most usually working during a 2-month summer program or during a single semester) and by working as novices in a research area, without years of experience with pattern recognition. The OEIS is a powerful tool to extend undergraduate researchers' reach and to help them make interesting conjectures and connections between their problems and others. In this talk, I will discuss several (mostly combinatorial) undergraduate research problems and highlight the key links OEIS helped students make.


Jeffrey Shallit, University of Waterloo

Title: 40 Years with Sloane's Integer Sequences

In this talk I will discuss some of my favorite discoveries made with the assistance of Neil Sloane's Handbook (Encyclopedia, On-Line Encyclopedia) of Integer Sequences over the last 40 years.


Neil J. A. Sloane, The OEIS Foundation and Rutgers University

Title: The OEIS: The Major Problems

There are several kinds of problem. (1) "Catalan or Collatz?" Are these sequences really hard, or are we overlooking something? For example, Leroy Quet's A134204, or van Eck's A181391. There has been progress: Kaprekar's 60-year old A006064 was recently solved. (2) "Low-hanging fruit" - recent sequences that cry out to be analyzed. (3) Should we try to raise an endowment, so we can hire a manager? (3) Need more music, animations, videos (demonstrations); increase accessibility by high-school teachers and students.


Michael Somos

Title: Multilinear Recurrence Relation Sequences

The study of recurrence relation sequences goes back to the ancient Greeks. Until recently, the main focus of study was on linear recurrences with constant coefficients, but a natural path leads to nonlinear recurrences, and among those there are multilinear recurrences. For example, the Catalan numbers satisfy

  0 = a(n)*(16*a(n+1) - 10*a(n+2)) + a(n+1)*(2*a(n+1) + a(n+2))

for all integer n except n=-1. Another example is

  0 = a(n)*a(n+4) - a(n+1)*a(n+3) - a(n+2)*a(n+2)

for all integer n satisfied by the Somos-4 sequence.
These two examples are homogeneous, but there are natural examples of nonhomogeneous recurrences such as

  1 = -a(n)*a(n+2) + a(n+1)*a(n+1)

where a(n)=F(2*n) [A001906] for all integer n.

Natural projects are to search the OEIS for sequences that satisfy homogenous or nonhomogenous multilinear recurrence relations with constant coefficients, and to find new sequences of these kinds with interesting properties. I have new results to report in this area.


Richard Stanley, MIT

Title: Some Catalan musings

The Catalan numbers 1, 1, 2, 5, 14, 42, 132, ... comprise entry A000108 of OEIS. The Comments to this entry includes the sentence "This is probably the longest entry in the OEIS, and rightly so." We will discuss a hodgepodge of different aspects of Catalan numbers to try to convey the richness and diversity of this famous sequence.


Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on August 13, 2014.