Sorensons
ResearchUnleashed

Algorithmic Number Theory Research Runs in the Family at Butler

BY Tim Brouk

PUBLISHED ON Dec 13 2019

It’s daughter-like-father when it comes to algorithmic number theory at Butler University.

Long before algorithms organized that cat video content you crave on your social media feeds, mathematicians and computer scientists created and utilized algorithms for faster and more precise calculations. The Department of Computer Science studies these algorithms to improve on existing methodology or to create new ways to compute.

Butler Computer Science Professor Jonathan Sorenson and his daughter, senior Brianna Sorenson, decided to take on Hungarian mathematician Paul Erdos and American mathematician John Selfridge’s 1974 algorithmic function for calculating prime factors of binomial coefficients. The research explored the possibilities of the 45-year-old problem. Father and daughter sought to expand the possible solutions and the speed in solving the problem, which hadn’t been challenged since 1999. With decades of computing breakthroughs at their disposal, the Sorensons got to work in the summer of 2018. 

“Algorithmic means you have problems in the area of number theory and you want to solve them using computer algorithms. The object of study is those computer algorithms,” Jonathan Sorenson says.

The Sorensons’ paper, An Algorithm and Estimates for the Erdos-Selfridge Function, will be submitted this winter to the 2020 Algorithmic Number Theory Symposium (ANTS), which is set for June 30 to July 4 in Auckland, New Zealand. 

Established by Cornell University as an intersection of mathematics and computer science fields, ANTS is the place where researchers explore the possibilities of challenging number theoretic problems like the Erdos and Selfridge problem the Sorensons studied, which identifies g (k) as the least integer bigger than k + 1 such that the binomial coefficient C(g(k), k) has no prime divisors larger than k.

Previous researchers computed the first 200 values of the Erdos-Selfridge function. In collaboration with Mathematics and Actuarial Science Professor Jonathan Webster, the Sorensons coded an original algorithm for faster computation for the problem. The work was successful as 157 more known binomial coefficients were discovered. That was almost twice as many numbers that mathematicians and computer scientists previously found.

“The 356th is 31 digits long,” Jon Sorenson says, “and it is the smallest such example larger than 357.”

The work was moved to the Big Dawg cluster supercomputer, which did the heavy lifting with the code written by the Butler team. The supercomputer took 12 days to find integer No. 355 but No. 356 was discovered four days later. Big Dawg had been working since Nov. 11 to find integer No. 357 and it finally discovered g(357)=2808033466727432757706599807359 almost a month later.

Binomial coefficients can break calculators when they reach as high as the Butler team took them to explore Erdos and Selfridge’s function. Jon Sorenson explains the process:

“If you have 10 different hats in your closet, then the binomial coefficient C(10,3) is the number of ways of selecting 3 hats from your closet. This is 120. There are 10 choices for the first hat, then 9 for the second, then 8 for the third, so 10*9*8.  But order doesn't matter, so we have to divide by the number of ways of rearranging 3 things, which is 3!=6. We get 10*9*8/6=120.”

A Computer Science and Mathematics major, Brianna Sorenson’s talent at solving problems with binomial coefficients led to the Erdos-Selfridge function research idea before the 2018 ANTS, which her father co-chaired. Only 19 years old at the time, she noted the function had been untouched since 1999. Why not explore it after 20 years of technological advancement and mathematical discovery?

The younger Sorenson spoke on the Erdos-Selfridge Function work at The Ohio State University Young Mathematicians Conference in August. The event was competitive to get into but Sorenson impressed with her algorithmic number theory work. The experience has been key as the senior prepares her graduate school applications, and being “alphabetically superior,” the younger Sorenson will be listed first.

“I can say ‘Look at this paper I’m in,’” Brianna Sorenson says with a laugh. “I think it’s really helpful to get this kind of experience. I’m wanting to get a PhD in computer science and that involves doing research and writing a thesis. This research was sort of a preview to it.”

Webster also collaborated with senior David Purdum, a Computer Science, Mathematics, and Statistics major, on a research paper, which will be submitted for ANTS 2020. Algorithms for the Multiplication Table Problem explores new ways to solve classic multiplication tables. By helping produce these papers, Purdum and Brianna Sorenson received experience that no coursework could provide. The process of publishing in the field of algorithmic number theory takes years, from selecting the problem to the final peer review of the paper. 

“This is intense and original thinking,” Webster says. “Each of these projects from start to finish take more than two years. With these multi-year projects, it’s difficult to see them through.”

By identifying the problems early in their Butler careers, Purdum and Brianna Sorrenson can count on submitting their high-level research as highlights to their final year as undergrads two years later. 

And for Jon Sorenson, he can count working with his daughter on high-level algorithmic number theory as a career highlight.

“You don’t often get to publish a paper with your kid,” the professor says. “It’s a dream come true.”

 

Media Contact:
Tim Brouk
Senior News Content Manager
tbrouk@butler.edu
765-977-3931 (cell)

 

Student Access and Success

At the heart of Butler Beyond is a desire to increase student access and success, putting a Butler education within reach of all who desire to pursue it. With a focus on enhancing the overall student experience that is foundational to a Butler education, gifts to this pillar will grow student scholarships, elevate student support services, expand experiential learning opportunities, and more. Learn more, make a gift, and read other stories like this one at beyond.butler.edu.

Algorithmic Number Theory Research Runs in the Family at Butler

Professor Jon Sorenson and daughter, senior Brianna Sorenson, tackle high math for international conference