2016 Projects

2016 Program Publications and New Submissions to the OEIS Database

Benjamin, N. (REU16), “Edge-distinguishing Chromatic Number of Ladder Graphs with 2n Vertices,” OEIS (A278375), November 2016

Benjamin, N. (REU16), Fiorini, E., Jaramillo Rodriguez, E. (REU16), Jovinelly, E., “Unique Integers on the Catalan Triangle,” OEIS (A275481), July 2016

Benjamin, N. (REU16), Fiorini, E., Jaramillo Rodriguez, E. (REU16), Jovinelly, E., “Non-unique Integers on the Catalan Triangle,” OEIS (A275586), July 2016

Brazelton, T.(REU16), Harrington, J., Kannan, S. (REU16), and Litman, M. (REU16) “On Consecutive Primitive nth Roots of Unity Modulo q,” Journal of Number Theory, Spring 2017.

Ediger, A. (REU16), “First Differences of A002960,” OEIS (A274004), June 2016

Moon, J. (REU16), Myers, K., Winkeler, Z. (REU16), “Numbers n with N-Position in the Edge-delete Game on the Path P_{n},” OEIS (A274161), July 2016

 

A Summary of 2016 Project Results

Project 16.02: Graph Theory and Combinatorial Projects (mentors: Myers & Fiorini)

Graph theory, and more generally combinatorics, is a natural connection to the OEIS. The program will explore several projects related to graph theory and combinatorics. Some examples include the following.

What (possibly finite) sequences can be generated based on graphs of size nn and order mm? For example, given some graph property pp, what sequences can be generated by this property? Let k be a positive integer and let G be a graph on n vertices with m edges. Let = λk(G) be the minimum number of edges to be deleted so that all the components of G that remain have less than k vertices. What is the minimum (or maximum) value of λk for all graphs G with n vertices and m edges? The resulting sequence considers m as a function of n.

There are several interesting sequences resulting from combinatorial problems on graphs. Could this procedure be extended to other structures such as fractals? Often these sequences do not converge, but have some cyclic pattern. Is it possible to “transform” a common sequence to some fractal pattern and determine if it converges?

Results: Expansions on “A Game of Edge Removal on Graphs”
The team of Alisa Ediger (MCMCS REU 2016, Tabor College), Jennifer Moon (MCMCS REU 2016, Grand Valley State University), Cindy Mora (MCMCS REU 2016, San Diego City College), Lyndsey Wong (MCMCS REU 2016, University of La Verne), and Huong Vu (MCMCS REU 2016, American River College) expanded upon a result by Gallant, et al, “A Game of Edge Removal on Graphs.” The original game involved two players being presented with a finite, simple, undirected graph with no isolated vertices. The players alternate making legal moves, which consists of removing an edge without it resulting in an isolated vertex. The last player able to remove an edge without it resulting in an isolated vertex is the winner. The team expanded on the results taking into consideration a variety of families of graphs as well as variations on the rules of the game. One variation involved vertex removal. The team proved that for graphs of even order, the game of vertex removal is in P-position (player 1 wins) and for graphs of odd order, the game of vertex removal is in N-position (player 2 wins). The team also produced results for a game of mixed removal (edges and vertices removed). These results were presented at several national and regional conferences and seminars including the 2017 Koint Mathematics Meeting in Atlanta, GA, the MAA Southern California-Nevada Sectional Meeting, and the Nebraska Conference for Undergraduate Women in Mathematics.

 

Project 16.04: Generation of Pythagorean triples (mentors: Cha & Myers)

An integer triple (a,b,c) is called a primitive pythagorean triple (A081874, A081925, A020882) when they are coprime and satisfy the equation a+ b2 = c2. One known method of generating all such triples is to use matrix multiplication. We will try to generalize this method to find all primitive integer triples (a,b,c) satisfying other homogeneous quadratic equations in a, b, c. Tools will be drawn from elementary number theory and linear algebra.

Results: Generalization on Pythagorean Triples and Dynamical systems
It is well-known that all the positive integer triples (x, y, z) without common factor satisfying x2+ y2 =z2 (called primitive Pythagorean triples) can be given a certain tree-like structure (or a directed graph) under the action of three fixed invertible matrices of integer coefficients. Recent work of Romik provides a new framework of creating a dynamical system from such a tree of primitive Pythagorean triples. Moreover, a generalization this tree structure has been recently discovered and there are now new trees known for other quadratic forms, such as x2+xy+y2- z2 and x2+y2+z2-w2. Using these new trees, the team of  Using this idea, the team of Edgar Jaramillo Rodriguez (MCMCS REU 2016, UC-Berkeley), Nathaniel Benjamin (MCMCS REU 2016, Kutztown University), Nathandis Wyley (MCMCS REU 2016, San Diego City College), Huong Vu (MCMCS REU 2016, Contra Costa College), Zachary Winkeler (MCMCS REU 2016, Northeastern University), Grace Ohanian (MCMCS REU 2016, Muhlenberg College), and Arian Reyes (MCMCS REU 2016, San Diego City College) created similar dynamical systems, generalizing the work of Romik. In particular, the symbolics of newly obtained dynamical systems turned out to have much in common with Romik’s system. The findings were presented at the 2017 Joint Mathematics Meeting in Atlanta, GA, and poster sessions.

 

Project 16.06: Variations on the Sieve Question (mentors: Fiorini & Shank)

The most famous sieve is the sieve of Eratosthenes. This is a simple algorithm for finding all prime numbers up to a given bound. That is, it is a process by which members of a list are eliminated by a well-defined set of rules until only a desired subset remains. This project would look at several general questions of a subclass of sieves. For example, given a sequence, is it possible to find a sieve that produces that sequence? Another example would be: Are there other classes of algorithms (sieve-like) for producing sequences?

Results: Unique Integers on the Catalan Triangle
The Catalan triangle is the number triangle whose entries, denoted c(n,k), give the number of strings with n X’s and k Y’s, where n,k∈N, such that no initial segment has more Y’s than X’s. While it is easy to show that every positive integer appears at least once on the Catalan triangle, very little was known about which integers appeared uniquely. The team of Edgar Jaramillo Rodriguez (MCMCS REU 2016, UC-Berkeley), Nathaniel Benjamin (MCMCS REU 2016, Kutztown University), and Eric Jovinelly (MCMCS REU 2016, Muhlenberg College), mentored by Dr. Eugene Fiorini, developed an algorithm to determine whether a given integer is unique on the triangle. Furthermore, the team proved necessary and sufficient conditions that guarantee uniqueness if met. The team also proved several subsequences appear uniquely in the triangle. For example, all primes appear uniquely except for 2 and 5. Additionally, for all natural numbers k≥3, c(k,k)≠pi for prime p≠2,5 and i∈N. As a result of the work this summer, the team had several new sequences accepted to the Online Encyclopedia of Integer Sequences. The team is currently preparing a paper to be submitted to the Journal of Number Theory. The team has also presented their results at several national and regional conferences and seminars including the 2017 Joint Mathematics Meeting in Atlanta, GA, and the Young Mathematicians Conference at Ohio State University.

 

Project 16.07: Sierpinski Numbers (mentors: Joshua & Byungchul)

An odd integer k is called a Sierpinski number if k2n + 1 is composite for all positive integers n. Let u and v be relatively prime integers. Given starting values a1 and a2, consider the recurrence relation an+1 = uan + van-1. What conditions can be placed on u and v to guarantee that at least one Sierpinski number appears in the sequence {an}? For example, if u = v =1 and a1 = 1 and a2 = 2, then {an} is the Fibonacci sequence and it has been shown that this sequence contains infinitely many Sierpinski numbers. The following is a list of other specific recurrence sequences that might be considered.

  1. Consider the Diophantine equation 

    1 + 2 + 3 + ... + (a - 1) = (a + 1) + (a + 2) + ... + (a + r).

    Let the set {(an,rn)} be the solutions to this equation. The sequence {an} is called the sequence of Balancing numbers and satisfies the recurrence relations a1 = 1, a2 = 6, an+1 = 6an - an-1.

  2. The sequence of Pell numbers satisfies the recurrence relations a1 = 1, a2 = 2, an = 2an-1 + an-2.

Results: Linear Recurrences and Covering Systems
Polignac conjectured that every odd positive integer can be written in the form of 2n+p for a positive integern. This would later be disproved by Erdos. Later it would be shown that there are infinitely many integers that cannot be written in the form of Fn+2n±1. Using this idea, the team of Tommy Brazelton (MCMCS REU 2016, Johns Hopkins University), William Britt (MCMCS REU 2016, Muhlenberg College), Abby Larson (MCMCS REU 2016, Valparaiso University), Siddarth Kannan (MCMCS REU 2016, Pomona College), Nathandis Wyley (MCMCS REU 2016, San Diego City College), and Lindsey Wong (MCMCS REU 2016, University of La Verne) applied this conjecture to both the Lucas and Pell sequences. After applying this idea the team also investigated other linear recursion sequences and the possibility of using covering systems to further uncover properties of these sequences. These results were presented at several national and regional conferences and seminars.

 

Project 16.08: Arithmetic Progressions (mentors: Hammer & Harrington)

Let A = {an} be a sequence of positive integers. Let Bm be a subset of m consecutive terms of A. We say that Bm has property P1 if there exists an ai ∈ Bm such that gcd(aj , ai) = 1 for all aj ∈ Bm with i ≠ j. Now let G(A) be the smallest positive integer, if it exists, such that there exists some Bm that does not satisfy property P1. For example, if A is the set of positive integers, then G(A) > 2 since no two consecutive integers have a factor in common. In fact, it has been shown that if A = {1, 2, 3, . . .} is the sequence of all positive integers, then G(A) = 17. The value of G(A) has been investigated for various other sequences including arithmetic progressions and Lucas sequences. This can be investigated for other sequences. For example, can we find the value of G(A2) where A2 = {Comb(2,2), Comb(3,2), Comb(4,2), ...}? If we let Aj = {Comb(j,j), Comb(j + 1,j), Comb(j + 2,3), ...}, what can be said about the sequence B(Aj)?

Results: On Consecutive Primitive Nth Roots of Unity Modulo q
Given a natural number n, the REU team of Thomas Brazelton (MCMCS REU 2016, Johns Hopkins University), Siddarth Kannon (MCMCS REU 2016, Pomona College), and Matthew Littman (MCMCS REU 2016, Penn State University) worked with mentors Dr. Joshua Harrington and Dr. James Hammer studying the conditions under which a finite field of prime order q will have adjacent elements of multiplicative order n. In particular, they analyzed the resultant of the cyclotomic polynomial Φn(x) with Φn(x+1), and exhibit Lucas and Mersenne divisors of this quantity. For each n≠1,2,3,6, the team proved the existence of a prime qn for which there is an element α∈Zqn, where α and α+1 both have multiplicative order n. Additionally, the team used algebraic norms to set analytic upper bounds on the size and quantity of these primes. The team submitted a paper with their results to the Journal of Number Theory, which was accepted and will appear in a spring 2017 issue. The team has also presented their results at several national and international conferences and seminars. 

 

Project 16.09: Game Theory (mentors: Shank & Hammer)

In this project we will begin by exploring classic game theory problems and learn strategic play and information. Then we will use these games and develop our own games in order to generate new sequences or find new descriptions for existing sequences.

For example, consider the following well known modification of the popular two-player game of Nim:

Assume there are two piles of pebbles with n pebbles and m pebbles where 0 ≤ n ≤ m.  We will denote this phase of the game as (n,m).   On a players turn, they may remove any positive number of pebbles from one pile, OR remove an equal positive number of pebbles from both piles.  Thus we may be left with phase (n-x, m), (n, m-y), or (n-z, m-z) with 0 < x ≤ n, 0 < y ≤ m, and 0 < z ≤ n.  The person that removes the last pebble wins the game.  Assume both players play optimally.  Notice if it is your turn on phase (0, a) or (a,a), then you have a winning strategy.  You can also deduce that if it is your turn on (1,2), then you will lose.  Similarly, the phase (3,5) is a losing phase.  (Can you find the next losing phase?) These pairs are called Wythoff pairs, which can be used to generate sequences.  (See for example:  A004481, A001954, or A128975).  There have been many different variations or extensions of this game including increasing the number of piles to changing the rules about removing (or adding!) pebbles. 

This project will allow you to be creative - creating your own games based on some simple rules.  Then we will generate sequences based on the games and extensions or variations of the game. 

Results: Expansions on “A Game of Edge Removal on Graphs”
The team of Alisa Ediger (MCMCS REU 2016, Tabor College), Jennifer Moon (MCMCS REU 2016, Grand Valley State University), Cindy Mora (MCMCS REU 2016, San Diego City College), Lyndsey Wong (MCMCS REU 2016, University of La Verne), and Huong Vu (MCMCS REU 2016, American River College) expanded upon a result by Gallant, et al, “A Game of Edge Removal on Graphs.” The original game involved two players being presented with a finite, simple, undirected graph with no isolated vertices. The players alternate making legal moves, which consists of removing an edge without it resulting in an isolated vertex. The last player able to remove an edge without it resulting in an isolated vertex is the winner. The team expanded on the results taking into consideration a variety of families of graphs as well as variations on the rules of the game. One variation involved vertex removal. The team proved that for graphs of even order, the game of vertex removal is in P-position (player 1 wins) and for graphs of odd order, the game of vertex removal is in N-position (player 2 wins). The team also produced results for a game of mixed removal (edges and vertices removed). These results were presented at several national and regional conferences and seminars including the 2017 Koint Mathematics Meeting in Atlanta, GA, the MAA Southern California-Nevada Sectional Meeting, and the Nebraska Conference for Undergraduate Women in Mathematics. 

 

Project 16.10: Statistical Analysis (mentors: Davidson & Fiorini)

Muhlenberg College is working with the Allentown Human Relations Commission to analyze data and develop statistical surveys that will better serve the Allentown community.