Where Do Those Undergraduate Divisibility Problems Come From?
The blog post by Chris Grossack examines undergraduate divisibility problems in polynomials, emphasizing combinatorial counting, the Pólya-Redfield theorem, and providing examples like bracelets and tic-tac-toe boards.
Read original article
The blog post by Chris Grossack explores the origins of undergraduate divisibility problems, particularly those involving polynomials that yield multiples of a specific integer. Grossack discusses how these problems often arise in introductory proof or discrete math classes, using the example of the polynomial \(P(n) = n^6 + n^3 + 2n^2 + 2n\), which is always divisible by 6. The author emphasizes the importance of combinatorial counting in ensuring that polynomial outputs are integers, suggesting that counting orbits of group actions can lead to such divisibility. The Pólya-Redfield counting theorem is introduced as a method to derive polynomials that are guaranteed to be divisible by the order of a group. Grossack provides examples, including counting the number of distinct bracelets and tic-tac-toe boards, to illustrate how these concepts apply in practice. The post concludes with a conjecture regarding the relationship between polynomials that are multiples of a fixed integer and their derivation from combinatorial counting methods.
- The blog discusses the origins of divisibility problems in undergraduate mathematics.
- It highlights the role of combinatorial counting in ensuring polynomial outputs are integers.
- The Pólya-Redfield counting theorem is presented as a method for deriving divisible polynomials.
- Examples include counting distinct bracelets and tic-tac-toe boards.
- A conjecture is proposed about the relationship between certain polynomials and combinatorial counting.
Related
Ordinals aren't much worse than Quaternions
The article explores the computability of ordinals up to ε₀, comparing them to quaternions and complex numbers, and discusses their unique properties, Python implementations, and recursive nature in mathematics.
Fibonacci Partial Sums Tricks
The paper discusses a mathematical trick for summing Fibonacci-like sequences, identifies the largest Fibonacci divisor of sums, and generalizes the method for Pell-like sequences, excluding Jacobsthal-like sequences.
A new rare high-rank elliptic curve, and an orchard of Diophantine equations
Recent developments in mathematics include Bogdan Grechuk's book on systematically solving Diophantine equations and the identification of a high-rank elliptic curve with 29 rational solutions, raising significant open problems.
Mathematicians Uncover a New Way to Count Prime Numbers
Mathematicians Ben Green and Mehtaab Sawhney proved there are infinitely many prime numbers of the form p² + 4q², utilizing the Gowers norm and building on previous conjectures in number theory.
Dice, (De)Convolution and Generating Functions
The blog post explores customizing dice, focusing on Sicherman Dice, probability distributions, polynomials for simulating rolls, convolution for understanding distributions, and generating functions for solving combinatorial problems.
8 commentsThere is a genre of undergraduate polynomial divisibility problems which look like this: Show that f(n) is divisible by some integer k.
These problems often appear to be (elementary) number theory problems. However, often there is a rather elegant proof associated with them which is based on combinatorics.
The crux of this proof is that the polynomial counts the number of equivalence classes of a certain kind.
This is closely related to https://en.wikipedia.org/wiki/Burnside%27s_lemma
The question at the end of the post is whether _all_ such problems must come this way
Exercise left to the reader:
Prove 7*n^3 + n is divisible by 2
because it's not true (simply insert 1, 2, 4 or 5)
the polynomial is =0 mod2 and =0 mod3 so its =0 mod6
n^6 + n^3 + 2n^2 + 2n (mod 2) = n^6 + n^3 + 0 + 0 = n^3(n^3+1) = 0*1 or 1*0 = 0
because consecutive numbers are even then odd then even ....
for mod3 you can make a table
you could also factor the polynomial and see the solution easily
n(n+1)(n^2-2n+2)(n^2+n+1)
Related
Ordinals aren't much worse than Quaternions
The article explores the computability of ordinals up to ε₀, comparing them to quaternions and complex numbers, and discusses their unique properties, Python implementations, and recursive nature in mathematics.
Fibonacci Partial Sums Tricks
The paper discusses a mathematical trick for summing Fibonacci-like sequences, identifies the largest Fibonacci divisor of sums, and generalizes the method for Pell-like sequences, excluding Jacobsthal-like sequences.
A new rare high-rank elliptic curve, and an orchard of Diophantine equations
Recent developments in mathematics include Bogdan Grechuk's book on systematically solving Diophantine equations and the identification of a high-rank elliptic curve with 29 rational solutions, raising significant open problems.
Mathematicians Uncover a New Way to Count Prime Numbers
Mathematicians Ben Green and Mehtaab Sawhney proved there are infinitely many prime numbers of the form p² + 4q², utilizing the Gowers norm and building on previous conjectures in number theory.
Dice, (De)Convolution and Generating Functions
The blog post explores customizing dice, focusing on Sicherman Dice, probability distributions, polynomials for simulating rolls, convolution for understanding distributions, and generating functions for solving combinatorial problems.