6 ms·
Where do those undergraduate divisibility problems come from?
- jmount 2y agoMore on integer valued polynomials: https://cameroncounts.wordpress.com/2017/01/31/polynomials-taking-integer-values/ https://cameroncounts.wordpress.com/2017/01/31/polynomials-t...
- svat 2y agoThat blog post is specifically about the question about whether a polynomial taking integer values on positive integers (or any sufficiently large subset thereof) necessarily is an integer-valued polynomial (the answer is yes). The OP blog post here actually links to / points out there's an Wikipedia article on integer-valued polynomials: https://en.wikipedia.org/wiki/Integer-valued_polynomial https://en.wikipedia.org/wiki/Integer-valued_polynomial Among other things, as mentioned, “every integer-valued polynomial can be written as an integer linear combination of binomial coefficients” [in exactly one way]. The conjecture in the OP post, that every polynomial everywhere divisible by k counts {something}, is intriguing, and I wouldn't be surprised if it were true.
- quasarj 2y ago[flagged]
- lqet 2y ago> That python code is horrid. Just out of curiosity, why do you find the code horrid? There are really only 9 lines of code that aren't glue code, and apart from the error prints (which are really irrelevant for these demonstration purposes), the code looks basically fine to me. EDIT: seen = [] for b in boards: if set(seen).isdisjoint(orbit(b)): seen.append(b) Ah, well... EDIT 2: also, see comment below, it's not Python
- mitchellpkt 2y agoedit: nevermind, it's sage code not python code
- IanCal 2y agoIt's not python, it's sage, so those actually work.
- boothby 2y agoSage is a Python (and the snippet you pasted works fine in Python). And I'm also curious what would qualify that code as "horrid." I'd make light suggestion to improve performance by making `seen` a set right off the bat, but for this size of problem, that sort of detail is unimportant. Calling somebody's code "horrid" without even understanding what it's doing isn't a productive approach to, well; anything, really.
- deleted 2y ago[deleted]
- quasarj 2y agoI was primarily offended by the second code snippet, in which there is a variable named foundException but it is not an exception. I didn't realize it was Sage (I didn't know that existed) but I'm not sure that actually makes a difference. Obviously it works, and that's fine, but it's still horribly ugly.
- GuB-42 2y agoYou perfectly summarized the reaction of any programmer looking at the work of a mathematician.
- hinkley 2y agoMath pages on Wikipedia have this bad. I don’t know whether the programming concepts pages are more sanely written or I already understand the circular reasoning. But it feels like they’re more approachable.
- rectang 2y agoThe math pages on Wikipedia value correctness above lay comprehensibility. It's easy to understand how this happens: a learned mathematician points out that a simplification for the purposes of making an explanation more approachable is not actually correct, so the explanation gets desimplified... and repeat ad absurdum until most math pages on Wikipedia cater primarily to experts and are too advanced for a good fraction of the audience.
- hinkley 2y agoBut why do experts need a wiki page?
- gopher_space 2y agoThe programming pages use symbols that exist on your keyboard and deconstruct their process. The math pages look like they’re trying to be Perl one-liners. Why is everything so jammed up, Mathematics?
- chongli 2y agoWhy is everything so jammed up, Mathematics? It's not. The language of mathematics is prose, usually written in English. The formulae are meant to illustrate the relationships in a very concise way but they're meaningless without the accompanying prose.
- jordigh 2y agoI don't believe your 99.9% figure. You surely know the syntax for multiplication, addition, and exponentiation. So you understand the polynomial in the opening paragraph. I'm sure you know function notation and division, so you understand that P(n)/k is always an integer. You probably have seen the sigma notation before because that's usually taught in high schools around the world, so you know that the lemma which is not Burnside's is about adding and dividing. You probably have seen the notation |X| to mean absolute value, so perhaps we finally are reaching the limits of your knowledge if it has been a while since you've seen the notation |X| can also mean the size of a set (which is, in a way, a sort of absolute value, mathematicians love type-punning). I'm sure you've seen function notation f: X -> Y to indicate that f is a function from the set X to the set Y, but I'll believe if you didn't know that [n] is the set {1, 2, 3, 4, ..., n}. I haven't done a careful calculation here, but I believe as a moderate estimate that this already covers at least 30% of the mathematical symbols in this page. My point is: the notation isn't probably the problem. You surely have seen these symbols before or can figure out what the individual symbols mean. I daresay the most esoteric symbol here is the Fraktur S for the symmetric group (here for the symmetric group of 6 symbols), https://en.wikipedia.org/wiki/Fraktur#Unicode https://en.wikipedia.org/wiki/Fraktur#Unicode but I assume that if you didn't know what the symmetric group is, the more common notation of S_6 would probably not have helped you much. So if the notation isn't the problem, I wager that the concepts and the difficulty of absorbing these ideas is the problem. It requires you to compile stuff yourself in your own head. With programming we are used to a machine doing this for us. We write the code, give it to a machine, the machine basically tells us if we're right or not. With mathematics we don't generally have that machine for all cases. You have to do the work in your own head. The problem isn't the symbols. The problem is that you have to think about them harder, work out what is being multiplied, what are the sets in question, what are the operations, and put them together yourself. You have to read something like not Burnside's lemma and understand what it's saying about permutations and sets and grouping and counting. Reading mathematics is a special skill. It's slow. It requires you to take out pen and paper and work it out yourself. Yes, like that. You have to do input and output on your own as you do mathematics. It's a unique skill that sadly isn't usually independently taught except at the university level. The concepts and the work required to understand them are the problem. Not the symbols. The symbols are superficial and easily dispensed with.
- dang 2y ago[stub for offtopicness]
- mjd 2y agoI feel silly saying this, but I wish the author would use more periods and fewer exclamation marks.
- deleted 2y ago[deleted]
- tromp 2y agoElaine Benes would be proud of their writing...
- leetcrew 2y agoI was in the pool!
- gazchop 2y agoOh this is nothing. One of my colleagues does that and adds random colour changes, underlines and font face changes. It's like working with a serial killer.
- gota 2y agoMaybe he was a teenager on IRC in the late 90s or early 00s and decided to never change Thinking about it I guess MSN messenger and My Space also allowed/encouraged font shenanigans? My memory falters
- andrepd 2y agoAhh. I honestly miss that amount of self-expression, garish as it was. Or rather, I intensely dislike the mono-culture where every vertical video with one-word subtitles looks the same.
- 2y ago
- np_tedious 2y agoWell I was curious, but there's a lot there I didn't understand. Apparently I'm good enough at math to do the proofs, but not to write the exercises. Exercise left to the reader: Prove 7*n^3 + n is divisible by 2
- abnry 2y ago7n^3 +n (mod 2) = 1 n^3 + n = n + n = 2*n = 0*n = 0
- BurningFrog 2y ago7*n^3 is even when n is even and odd otherwise. odd + odd is even, as is even + even.
- Spivak 2y agoThe easy way of seeing the first part is to do the prime factorization. The 7 doesn't matter since it's prime. If n has a 2 in its factorization it now has 2^3. But if it doesn't have a 2 it won't suddenly acquire one. All the symbol soup proofs aren't wrong but I don't think they satisfyingly explain the why.
- thaumasiotes 2y agoAll of these "always divisible by n" proofs are asking you to solve them case by case in modular arithmetic. For divisibility by two, there are only two cases. So if n is 1, then n³ is 1, and if n is 0, n³ is 0. 0+0 = 0; 1+1 = 0; and this completes the proof. I am not actually sure that doing a prime factorization on 7n³ for unknown n is easier than knowing that 1³ = 1.
- crabbone 2y agoI vote this the best proof. All you need to know to understand it is to know how multiplication, addition and exponentiation works. You could probably show this to a child in a sixth grade or so, and have them understand it. This is really good!
- 2y ago
- t43562 2y agoMy daily dose of inferiority: done. :-) Perfect sentences which are complete gobblede-gook to me.
- agnishom 2y agoTLDR Summary: There 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 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
- daef 2y agoi couldnt come up with a proof for the initial problem (n^6+n^3+2n^2 is a multiple of 6 for every n) because it's not true (simply insert 1, 2, 4 or 5)
- goldencoralefan 2y agoYou’re missing a term: n^6+n^3+2n^2+2n
- deleted 2y ago[deleted]
- nh23423fefe 2y agoi just computed the solution mod 2 and mod 3 a la chinese remainder theorem 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)