jmount 2 days ago
  • svat a day ago

    That 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

    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.

t43562 a day ago

My daily dose of inferiority: done. :-) Perfect sentences which are complete gobblede-gook to me.

agnishom a day ago

TLDR 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

The question at the end of the post is whether _all_ such problems must come this way

np_tedious 2 days ago

Well 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

  • MichaelRo a day ago

    >> Apparently I'm good enough at math to do the proofs, but not to write the exercises.

    Took a look on it, seems like a highly particular / specialized area of mathematics. It's like computer science, can't know them all. If you work all day with some area, say compilers or databases or financial software or what else, you'd be a whizz at it while it's unreasonable to expect someone from a different domain be able of more than a superficial understanding of what you write.

    I'm pretty good at math but like with computers, I don't have the compulsion to dive deep into an unfamiliar domain just for the sake of it. So commenting on the article: cool, now I know how these problems are formed and in the very unlikely domain I'll need to produce one, I know where to look. Likely this will never happen, though.

    • dleeftink a day ago

      > seems like a highly particular / specialized area of mathematics. It's like computer science, can't know them all

      As a non-mathy, I'm interested in whether the idea that being good/able to provide proofs in one area, automagically makes one proficient in another is customary in the field or rejected quite early on when choosing a math specialisation?

      • svat a day ago

        It is not typical that being good in one area of mathematics makes one proficient in another — mathematics has a lot of depth, and to reach the frontier in any specialization requires years of study. However:

        - There are skills that carry over; these are usually known by the name "mathematical maturity" https://en.wikipedia.org/w/index.php?title=Mathematical_matu...

        - There is a story/legend told about Erdős, where he was so good at problem-solving/proofs that he once solved a problem in another area after asking for the definitions of the terms in the problem. (The fact that this story is told illustrates that it is not commonplace.)

      • MichaelRo 21 hours ago

        Well there is common stuff that one must be familiar with to be proficient and marginal stuff that you can get by without knowing because chances is you're not going to need it.

        Like take for instance financial mathematics where I had some special interest, it's totally oblivious to areas such as geometry or number theory. I never had to figure out if a polynomial is divisible by 6 for instance :)

        Like computer science, there's the common algorithms stuff but being an expert in web development doesn't help you much in writing high frequency trading server code, and the other way around.

  • BurningFrog 2 days ago

    7*n^3 is even when n is even and odd otherwise.

    odd + odd is even, as is even + even.

    • crabbone a day ago

      I 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!

    • Spivak a day ago

      The 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 a day ago

        All 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.

  • svat a day ago

    > but not to write the exercises

    As the post mentions in passing, the integer-valued polynomials are completely characterized by the property that when written as a sum of {c_i (x choose i)}, all the coefficients c_i are integers. I imagine this is where most of the exercises actually come from. For example, using [3 1 4 1 5 9], the polynomial {3 + 1·x + 4·x(x-1)/2 + 1·x(x-1)(x-2)/6 + 5·x(x-1)(x-2)(x-3)/24 + 9·x(x-1)(x-2)(x-3)(x-4)/120} simplifies to 1/120 (9x^5 - 65x^4 + 185x^3 + 5x^2 - 14x + 360), so you could use it to generate exercises like:

    - Prove that 9x^5 - 65x^4 + 185x^3 + 5x^2 - 14x + 360 is always a multiple of 120

    (or 5, or any divisor of 120).

  • cherryteastain 2 days ago

    Given p(n) = 7n^3 + n:

    If n is even, we can choose some m such that n = 2m, and p(n) = p(2m) = 7 * 8m^3 + 2m = 2 * (7 * 4m^3 + m), which is divisible by 2 since we could factor out the 2 at the start.

    If n is odd, similarly we can say n = 2m + 1. p(2m) = 7 * (2m + 1)^3 + (2m + 1) = 56m^3 + 84m^2 + 44m + 8 = 2 * (28m^3 + 42m^2 + 22m + 4), which is also divisible by 2 per the 2 at the start.

  • abnry 2 days ago

    7n^3 +n (mod 2) = 1 n^3 + n = n + n = 2*n = 0*n = 0

  • deruta a day ago

    And a proof by "counting something":

    1 + 2 + ... + n = n(n+1)/2

    2 divides n(n+1), n(n+1) = 2m

    7 * n^3 + n =

    2*(3*n^3 + n) + n^3 - n =

    2*(3*n^3 + n) + n(n+1)(n-1) =

    2*(3*n^3 + n + m(n-1))

  • dh2022 a day ago

    n = 0 or 1 modulo 2. So we have to check out only two cases module 2, and these cases trivial. To prove the problem note that 6 = 2 * 3 and then is trivial to see that the polynomial is=0 modulo 2 if n=0,1 modulo 6and then check it is =0 modulo 3 for n=0,1,2 modulo 3 and you are done.

nh23423fefe 16 hours ago

i 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)

daef 21 hours ago

i 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)

dang 2 days ago

[stub for offtopicness]

  • mjd 2 days ago

    I feel silly saying this, but I wish the author would use more periods and fewer exclamation marks.

    • amne 2 days ago

      You're the second commenter, so far, to mention exclamation marks. What do they mean to you that would bother you so much to point it out, or anyone for that matter? I haven't even noticed them until I read the comments here on hn.

      • micaeked 2 days ago

        Not gp, but I feel similarly. For me, I can't help read it with emphasis. As in, the voice in my head gets all fancy in an annoying way. If you imagine someone in person reading it out-loud with exaggerated emphasis, that's what it feels like. Same thing with comic books for me, the sprinkled bolded words in dialog are really grating.

      • Etheryte 2 days ago

        To me it's fairly similar to someone making excessive use of CAPS LOCK. It can be used as a stylistic choice at times, but use it TOO MUCH and it just becomes DISTRACTING.

      • Minor49er 2 days ago

        I DON'T SEE A PROBLEM WITH THIS EITHER! BUT I EMPATHIZE! I GET COMMENTS FROM PEOPLE SAYING THAT I'M SOMEHOW YELLING AT THEM ALL THE TIME BUT I'M ACTUALLY SITTING IN SILENCE, TYPING QUIETLY ON A MEMBRANE KEYBOARD! LOL???

    • tromp 2 days ago

      Elaine Benes would be proud of their writing...

    • gazchop 2 days ago

      Oh 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 2 days ago

        Maybe 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 2 days ago

          Ahh. 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.

  • Etheryte 2 days ago

    [flagged]

    • bwfan123 2 days ago

      I beg to differ, I think the writing conveys beautifully, the deeper abstract ideas embedded in what appears to be a simple problem - hence, it captures the essential spirit of what math is about

    • LPisGood 2 days ago

      I like when the author’s personality shines through, and frankly I can’t imagine finding occasional exclamation marks _tedious_ of all things. I just don’t take things so seriously, I suppose.

quasarj 2 days ago

[flagged]

  • lqet 2 days 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

    • boothby 2 days ago

      Sage 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.

    • quasarj a day ago

      I 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.

      • lqet a day ago

        > named foundException but it is not an exception

        They don't mean "found an execution exception", they literally mean that the code found an exception to the rule that n^9 + 4n^6 + n^5 + 2n^3 is divisible by 8.

        • quasarj 17 hours ago

          Yeah I understand that. You still shouldn't do it.

    • mitchellpkt 2 days ago

      edit: nevermind, it's sage code not python code

      • IanCal 2 days ago

        It's not python, it's sage, so those actually work.

  • GuB-42 2 days ago

    You perfectly summarized the reaction of any programmer looking at the work of a mathematician.

    • hinkley 2 days ago

      Math 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.

      • chongli 2 days ago

        I love the math pages on Wikipedia but I have a math degree. They are written (written clearly and concisely) for mathematicians.

        If you're a programmer (but don't have a math degree) then I would offer up API docs as a comparison. They are written for you, the user of the API, to be as concise and straightforward as possible so that you can get up and running with the API. API docs are definitely not written for beginners who have never written a line of code (or a line of code in the language the API is written in) before.

        If there's one complaint I may entertain, it's that Wikipedia isn't supposed to be a resource for specialists. It's intended to be an encyclopedia for a general audience. But then by that reasoning, many of these math pages on Wikipedia probably ought to be deleted outright because they're simply too specialized in the first place. So we're left with the dilemma: do we keep these articles as-is (and keep mathematicians happy) or do we delete them outright because they're too specialized?

        The third option, rewriting them for a general audience, is likely to run afoul of Aesop's fable #721 "The miller, his son, and the donkey" [1]. You'll get a highly technical and complex article that explains far too much and buries its insights in overly verbose and cumbersome prose (which cannot assume any prerequisite mathematical knowledge). It'll please neither the mathematician nor the general audience member.

        [1] https://en.wikipedia.org/wiki/The_miller,_his_son_and_the_do...

      • rectang 2 days ago

        The 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 17 hours ago

          But why do experts need a wiki page?

      • gopher_space 2 days ago

        The 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 2 days ago

          Why 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.

          • hinkley 17 hours ago

            You know… when I took the SATs I surprised myself by scoring higher on verbal than math. But it has explained so much about my subsequent interactions with my fellow nerds. So many people don’t realize prose is part of their job description and it shows. Doubly so for mathematicians. I feel like I’m taking crazy pills until I have to talk to customers or consumers and I see how they think we are all collectively nuts. They’re not wrong.

            In software, restating the problem or the bullshit plainly is usually the first step to eliminating or mitigating it. George Carlin and his rants about softening words until they mean nothing comes to mind all too often.

  • jordigh 2 days ago

    I 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

    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.

    • quasarj a day ago

      I feel like it was obvious I was being hyperbolic about the 99.9% figure.

      But still, thank you for the long and thought-out reply. You're mostly right, of course, about the symbols I was familiar with. I didn't know about the "size of a set" using the |X| notation, that's new to me, but yeah.

      I've heard the explanation of "compiling it in your head" before, and it makes sense, and I think I get the idea. However, that's a ton of work to understand a post, and my ADHD is way too strong.

      I did go read about the lemma which is not Burnside's, though that lead down a rabbit hole (I had never heard of a lemma).

      Anyway, I think you're mostly right about all of this, but I do think the position of "it's not the symbols" is a common misconception. It's like you handed me a recipe book in Spanish, and I said I don't speak Spanish, and you said "well, the the book isn't really _about_ Spanish, you know"