During our morning meeting, Dr. Deters and I discovered that our solutions were completely different. His solution involved iterating through many different vectors, taking the product of each element in the vector, and recording the vector and the product on the computer. My solution, on the other hand, involved a game-like algorithm that generated a tree diagram of every possible Connect Four board, constrained by certain rules. We discussed our respective solutions, and we agreed that each of our solutions have distinct advantages. The advantage of my solution is that it allows the user to input any whole number and find all sets of whole numbers whose product equals the input number, without calculating the results of any other input number. His solution, on the other hand, requires looping through all sets of whole numbers, calculating the results of not only the input number, but all the numbers less than the input number as well. If our goal was to find every set of whole numbers whose product equals a specific number, or a small set of specific numbers, then my solution would be faster, because it wouldn't make any unnecessary calculations. However, our goal is to find every set of whole numbers whose product equals each number from 1 to 1024. Since we have so many target numbers, we agreed that his solution would be faster and easier to code, so I spent my day coding that solution. It's exciting how many ways there often are to solve a single mathematical problem!
I coded the solution in both Python and R, using a recursive algorithm that I designed. At first, I was having a hard time developing the recursive algorithm, because it was hard to keep track of the recursive data flow. To make this process easier, I tried hard-coding my algorithm for 2 layers of recursion, and later 3 layers of recursion. By the time I had coded 3 layers of recursion, I had a better understanding of the patters involved in the recursive algorithm, and I successfully coded an algorithm that produced the complete solution to the problem we'd spent over a week working on! I showed Dr. Deters my solution during our final meeting, and he was pleased with the progress we'd made. During our meeting, Dr. Deters gave me the opportunity to ask him any questions I had about a mathematical career. When I asked him about whether a PhD was required to be hired for a role in which I solve interesting mathematical problems in industry, he said that a PhD definitely wasn't required. He told me, in fact, that much of what he does on a day-to-day basis could be done by a competent undergraduate with good mathematical reasoning skills. Dr. Deters also told me that most mathematical research feels very much like what I've experienced in the past three weeks: trying out countless creative solutions, finally finding one that works, and then discovering that the solution you thought worked is actually incorrect. But with each incorrect solution, the mathematician's understanding of the problem grows, until the mathematician has developed a deep enough understanding to wrestle the problem to the ground and pin it down with a proof. Finally, he expressed that one of his favorite things about working in the field of mathematics is that countless different fields of "pure mathematics" often have remarkably broad applications in the real world. For instance, he and his colleagues used complex analysis to solve a geographical problem for the insurance industry, and proving that my Connect Four solution (and generalizing the solution) would require number theory. One of the most fun parts of day-to-day mathematical work is combining different mathematical tools to solve a problem in an original way. Overall, I think I've learned a ton about what a mathematical career is like, and I'm now even more strongly considering majoring in math in college.
0 Comments
I began today by putting into code my idea from yesterday. However, as I started implementing it, I realized that both Dr. Deters and I had missed an important case. If I finished putting this idea into code, running the code would give us part of the solution, but not the entire thing. Although I knew that I didn't have the full solution, I spent the day putting the partial solution we had into Python code, hoping that coding the partial solution would give me ideas for how to improve it. I didn't come up with any new insights as I was coding, and I made an excel document that showed exactly what was wrong so that I could clearly communicate with Dr. Deters when we met.
Dr. Deters and I spent an hour discussing various different ways to approach the problem, but we didn't make much progress. At the end of our meeting, we resolved to continue thinking about things and meet the next morning if either of us had any new ideas. That evening, during a run, I thought about nothing other this problem. As I weaved through the streets of Bowling Green, hardly aware of where I was going, I tried out idea after idea, figuring out exactly what was wrong with each incorrect idea I tried. Eventually, I came up with a plan for a simulation that would give us the solution. The plan was based off the game Connect Four, and it involved representing each prime number as a Connect Four tile and each column of the board as a place in the probability table combinations vector. When I got back to my car, I picked up my phone with the intent to text Dr. Deters about my idea. Coincidentally, right as I was about to send my message, he told me that he also had an idea and asked if meeting at 7 tomorrow morning would work. Of course, I eagerly said yes. I'm excited to meet tomorrow morning and compare our ideas! Before my meeting with Dr. Deters, I began assembling my small functions into a final function, but something wasn't quite right. I still wasn't generating every possible set of numbers that multiplied to produce the input number n, which means that I wasn't successfully finding each probability table that would have n elements. Additionally, I had coded my algorithm such that it threw away the majority of the combinations it generated because they were redundant, which meant that the algorithm wasn't as efficient as it could be. Because my algorithm wasn't working as I expected it to, I went back to paper and did some more math to try to think of a different approach. Although much of what I experimented with today didn't turn out to be directly applicable to this algorithm, it was still very interesting; at one point, I discovered a fascinating connection between the geometry of a tetrahedron (or any multidimensional shape in which all vertices are connected) and the combinatorial problem that lies at the heart of the problem I'm trying to solve.
During my meeting with Dr. Deters, I explained to him a few of the things I had been experimenting with. As we were talking, Dr. Deters had an excellent idea: rather than combining multiple partition vectors, we could partition each exponent individually, and then take every combination of every partition of each exponent vector. As we discussed this idea, we both felt that it was more correct than anything else we'd explored. I'll spend tomorrow integrating this idea into my algorithm! I started the day with a morning meeting with Dr. Deters, during which we discussed the progress I'd made on the problem and other ways to approach it. As we were talking, Dr. Deters suggested that some number theory concepts could be useful, and he asked me if I'd ever heard of a partition. When I said no, he explained that the partition of an integer n is a set of integers that sum to n. The number 4, for instance, can be partitioned in 5 ways: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}, and {4}. We discussed that the idea of partitions could be useful in this problem. Partitioning the exponents to which each prime factor of the number of elements k in a probability table could be crucial in identifying all possible multidimensional probability tables that could have k elements.
As I continued working on this algorithm today, I utilized the idea of partitions to make progress on finding an algorithm that solved the problem. I edited the algorithm to include a function that finds all the partitions of a each exponent, a function that pads the partition vector with zeros to allow all partition vectors to be added to each other, and a function that finds all possible permutations of each zero-padded partition vector. Tomorrow, I'll assemble all these functions into a final algorithm that I believe will solve the problem. After spending a while working on this problem on paper yesterday, I decided to approach it from a different angle today: by creating a Python program. In some ways, creating a Python program is a less mathematically rigorous way of solving the problem, because I don't accompany the program with any formal proof. However, I thought it would be a good way to make headway on the problem and further familiarize myself with the set of steps that will be necessary to eventually prove are appropriate.
My program is designed to find all possible combinations of numbers that multiply to produce an input number n. Order of multiplicands is unimportant. To find these combinations of numbers, I first split n into its prime factors. Then, for each prime factor in this list, I divide n by the prime factor and run the same function recursively on this new number. For instance, if my starting number is 42, my program splits 42 into its prime factors 2, 3, and 7. Then it divides 42 by the first factor, 2, creating the vector (2, 21). The program runs again on the rightmost number, 21, creating more vectors. After finishing with this vector, the program goes back and divides 42 by 3, creating the vector (3, 14). The same process repeats until all the component vectors are produced. My program isn't working perfectly yet, however, and I need to keep working on it tomorrow. Although it doesn't properly return each combination of multiplicand vectors, it does return the correct number of sets of numbers that can be multiplied to form any input number, so I think I'm on the right track. I began the day by meeting with Dr. Deters to learn about the next problem I'll be working on. This problem is also relevant to the probability table paper, through it involves more programming than proof writing (at least in the initial stages). I'll summarize the problem below.
When we think of a probability table, we usually think of a two-dimensional diagram, with one categorical variable on the horizontal axis and another on the vertical axis. However, it's possible to have probability tables of more than two dimensions as well. A probability table with three categorical variables, for instance, would be three-dimensional and look like a cube. This same idea can be extended to any number of dimensions. In any number of dimensions, the number of cells in the table equals the product of the number of categories in each categorical variable. For instance, a three-dimensional probability table in which variable 1 has 2 possible categories, variable 2 has 3 possible categories, and variable 3 has 4 possible categories would have 2*3*4, or 24, cells. It's important to note that a 2x3x4 table isn't the only possible table that could have 24 cells. A 2x12 table, a 4x6 table, a 3x8 table, or even a 2x3x2x2 table would all have 24 cells. My task is to find a mathematical process that allows us to easily discover all possible combinations of dimensions that would result in a probability table with n cells, where n is any natural number. There are many ways to go about solving this problem, and today I focused on a combinatorial approach. I spent several hours messing around with the numbers, trying out various ideas I had. I didn't come up with any promising solutions today, but I feel more familiar with the problem and am excited to continue working on it tomorrow. I spent today typing my proofs by induction into LaTeX, in addition to making several more edits. Throughout the proof, I had to change my notation a bit. You'll recall that I've been working with two functions that are inverse of one another, f and g. When I wrote f(g(v)) in my original proof, where v is a vector, I usually evaluated both functions for v and ended up with a long vector of numbers that I had to carry around. To make the proof more concise, I ended up changing these long vectors simply to (f(g(v)) and leaving them in this form until I absolutely needed to evaluate them. This change also made the proof's notation align more closely with the notation I used in my proof by induction, which makes the proof more mathematically rigorous as a whole.
I had a long meeting in which I showed Dr. Deters my edits, and he said that there was nothing else big that I need to change! I addressed all things I needed to show to complete the entire proof, and Dr. Deters said that my proof was mathematically correct. He'll make a few small edits to make the proof's presentation a bit more concise, but he said that I did most of the hard work that he didn't want to have to do. Tomorrow morning I'll meet with him to learn about the next section of the problem we're working on! I spent today experimenting with ways to use proof by induction to streamline an important part of my proof. I've read proofs by induction before, but I've never created one. Dr. Deters explained it effectively using the following analogy.
To prove by induction that a set of dominos falls, the following things must be proven: 1) the first domino falls, and 2) if the kth domino falls, than the (k+1)th domino falls, where k is between 1 and the number of dominos in the row. The same reasoning can be applied to summation or product equations. I must first prove that the equation is true when k=1, and then I must prove that if the equation is true for some value k, then the equation is also true for k+1. I spent the day messing around with the equations I've generated, trying to establish these facts for each of them. Eventually, I hit what I thought was an impasse. I would start by assuming that the equation was true for k. Then, I would write the conclusion equation with k+1. From the conclusion equation, I would try to generate an obviously true mathematical fact, like 1=1, substituting information from the assumed k equation if necessary. However, the k+1 equation kept simplifying to the assumed k equation. I wasn't satisfied with this, because I thought that this simplification to the assumed k equation represented circular reasoning. However, Dr. Deters explained that this is actually how proof by induction is supposed to work. It doesn't matter whether the k equation is true; it only matters whether the k+1 equation is true for any k, as long as we've already established that the k equation is true when k=1. For instance, if we somehow established that 1=2, we could use induction to show that 2=3, and so on. The reason we can't construct a real proof by induction of this fact is because we can never prove the base case: we can't prove that 0=1, because it isn't true. Now that I have a better understanding of proof by induction, I'll incorporate what I've done today into the rest of my proof, and I'll add it to the LaTeX document tomorrow. Today I had the longest meeting I've had with Dr. Deters so far–almost 2 hours! We extensively discussed the progress I made on my proof, and he suggested plenty of further revisions. One general area in which I can improve is the order in which I present my arguments in proofs. In my draft, I often started with the conclusion, and I derived the given information from the conclusion. However, Dr. Deters explained to me that it's often easier for the reader to understand my logic if I start with the given and work my way to the conclusion. Dr. Deters acknowledged that it is often easier to generate a proof by starting at the conclusion, playing around with the conclusion's mathematical implications to try to find a way back to the given information. However, it's often better to present a proof in the opposite direction, starting with the given. This suggestion makes sense to me, and I will edit the proof accordingly. Although he had many suggestions for things I should improve about the proof, he said that I was on the right track overall and praised the progress I've made.
Before our meeting, I began learning the programming language R, which I may use to implement some of the concepts I'm proving after I finish the proof. I already have experience in using Python for data science, so learning the basics of R is straightforward. I focused on creating and manipulating dataframes and lists in R, and I also learned basic R syntax, including how to define variables and functions. I already understand all these concepts from my work in Python, so learning syntax wasn't difficult. Tomorrow, I'll work on implementing some of the revisions we discussed in our meeting today. I spent most of today converting the proof revisions I wrote in my notebook into LaTeX code. By the end, I had produced a 7 page document! This is by far the longest mathematical document I've ever produced.
I discovered something interesting as I was typing my work into LaTeX: presenting my notebook's contents in a way that was meant to be readable to anyone forced me to strengthen many of my own ideas. When working in my notebook, it's easy to get away with slightly "hand-wavy" definitions or lines of reasoning when I know what's going on. However, the slow process of typesetting in LaTeX forces me to seriously consider every character I type. Typing in LaTeX is to writing as handwriting notes is to typing notes; the slower option forces me to think more clearly. In fact, when I mentioned this discovery to Dr. Deters, he told me that he used to practice for his PhD exams by typing the solutions of past exams into LaTeX, rather than simply writing them out. He suggested that I do the same during my undergraduate mathematics studies when I want to understand a concept especially deeply. On Monday, I'll meet with Dr. Deters to get feedback on this set of proof revisions and prepare to write my next draft of the proof! |
Jeremy MahoneyAspiring data scientist, Impromptu teacher, Lover of learning, and admirer of the universe ArchivesCategories |