> In the quote below, he names the AND function "f", which in itself is a bit strange. What's wrong with "and" or ∧?

'∧' usually denotes the logical AND operator, which does not operate on integer values, (i.e. writing 22 ∧ 78 = 6 is weird). So it's not a bad idea to give this function a different name.

He could have made that explicit though.

I think you're right. By definition it can't have any more 1's that the lesser has and it might have less 1's than the lesser has.

You're correct, it can be changed to `min(a, b)`. A rough proof:

* assume WLOG `a = min(a, b)`

* `a & b` takes the set bits of `a` and produces a subset of them

* the value of an integer is `SUM 2^j` where the j-th bit is set

* removing positive elements from a sum can only make it smaller

* therefore & can only produce a value smaller than `a` (the minimum)

There is not, and there cannot be. However, even if he was figuring this all out from scratch, he could not have come up with the hand-written charts without realizing that.

I'm going to go out on a limb and guess that it is of some habitual relevance to a mathematician, since he mentions the identity function (not really relevant here either), but that the material he actually explains here doesn't do anything to justify its appearance.

However, I cannot present to you the crucial difference between the maximum of two numbers and the minimum of two numbers that explains what he was thinking. This must exist for my hypothesized explanation to make sense.

> I'm going to go out on a limb and guess that it is of some habitual relevance to a mathematician, since he mentions the identity function (not really relevant here either), but that the material he actually explains here doesn't do anything to justify its appearance.

It's worse than that; he mentions the identity function only to make a gross error about it. The identity function on (a, a) is (a, a), not a.

I don't think you need to be so unforgiving?

If you want extra precision, a -> f(a, a) is Id.

Knowing that helped me understand one property of the chart, never said that was the most stunning of properties, and the best articulated one :-)

The law x AND 1 = x is called the identity law.

The law x AND x = x is called the idempotence law.

Nothing to do with the identity function.

> If you want extra precision, a -> f(a, a) is Id.

What does this mean?

The function which to any integer a associates f(a, a) with f defined as in the article is the identity function on the natural integer set.

Granted. g(a) = f(a,a) is indeed the identity function for all f such that f(a,a) = a. That seems pretty pointless as an observation. We have f, so we're observing that some other, unrelated function is the identity function?

Assuming you actually care about the answer, this just help me drew the exploratory graph, and this property was useful to fill in cells for which operands were equal. Finding obvious properties is a great way to learn a pattern without even computing things. Unlike what you may think, I had no idea what I was about to find - I had never seen this chart drawn before, and so this post is structured around how I thought about the exploration, not around how it may be presented to an audience who already knows way more than I do on bitwise operations. Sounds fair?

Sure it's fair. Bitwise operations produce pretty strange numeric results, so no, I wouldn't think you'd expect much going in. But I don't see where the identity function comes into it at all. It looks like the term "the identity function" stuck in your mind, and you reached for it when you found something subjectively similar. But shared semantic space isn't a good reason to say that a function which isn't the identity function, is. Your middle point is the observation "f(a,a) = a", which is perfectly valid, but is not the same finding as the finding you report. Using pretty-simple terms to state something true is generally preferable to using even simpler terms to state something false.

It is fair enough, that you find the law f(a,a) = a useful. Just don't call it the identity function when it is not.

A counterexample is 0 & -1 == 0.

The given function is clearly only defined over naturals. In the first part using bits, there's no indication of how to encode negatives, and in the second part with the sum equation, f(-1,-1) >= 0 (and thus not equal to -1) for any reasonable definition of the modulo function paired with any `b`, which breaks one of the stated identities. In fact, that's true if you replace mod with _any_ function.

> The given function is clearly only defined over naturals.

The post doesn't specify. Programming languages do define it over the negatives, however. I just didn't want anyone going into python and asserting that a & b >= min(a,b).

> there's no indication of how to encode negatives

Just do the standard thing: use 2s complement arithmetic [1]. More concretely: set b to infinity and take the limit under the 2-adic metric [2]. For example, -2 & -1 has partial sums 0, 10, 110, 1110, 11110, etc. It's limiting to ...1111110, which is the 2's complement representation of -2.

1: https://en.wikipedia.org/wiki/Two%27s_complement

2: https://en.wikipedia.org/wiki/P-adic_number

The laws given in the post were explicitly derived from the equation. Please explain how you used that to determine f(0, -1)?

Pick any `b` you want, even infinity, and evaluate:

    sum_n^b 2^n (floor(0/2^n) mod 2) (floor(-1/2^n) mod 2)

    sum_n^b 2^n * 0 * 1

    sum_n^b 0

    0

Excellent. I'm glad we agree. You'll notice that the stated identity f(x,x) = x fails to hold over x < 0. I hope this is sufficient to make it clear that the equation does not consider the negatives?

Seems to work fine for -1:

    f(-1, -1)
    = sum_{n=0}^b 2^n (floor(-1/2^n) mod 2) (floor(-1/2^n) mod 2)
    = sum_{n=0}^b 2^n * 1 * 1
    = 1 + 10 + 100 + 1000 + ... [in binary]
    = ...11111 [in the 2-adics]
    = -1

I'm not quite sure they have enough paper for numbers with infinite boolean expansions.

Yeah for an AND function, f(a,b) <= min(a,b)