Real Analysis – Dyadic Squares and Rigorous Proof Writing

Question

I have been working my way through an exercise from Pugh's "Real Mathematical Analysis" which asks me to prove that two dyadic squares in $\mathbb{R}^2$ of same size either intersect along a common edge, have a common vertex, are the same or are disjoint. It seems intuitively obvious to me (and I have made some progress in the proof as well), but I struggle with rigorously writing it down. Here's how far I got.

Intuition/Explanation

Dyadic cubes are fairly easy to explain: a dyadic cube in $\Bbb R^m$ is the cartesian product of $m$ intervals of same length, with the catch that the interval can be written as $[\frac{a}{2^k}, \frac{a+1}{2^k}]$, with $a\in\mathbb{Z}$ and $k\in\mathbb{N}$ including $k = 0$. So for example, $[\frac{a}{2^k}, \frac{a+1}{2^k}]\times[\frac{b}{2^k}, \frac{b+1}{2^k}]$ would be an example of a planar dyadic cube (dyadic square) as the length of both intervals is the same, namely $\frac{1}{2^k}$.

My idea has been that if there was a common point $x$ in any 2 different dyadic squares which is neither on a common edge nor vertex, then I could show that one of the squares would have their edge along a "coordinate line" which is not a dyadic number. To show what I mean, I attached the image below:

Suppose the green square was an ordinary dyadic square. My assumption is that if there was a square such as the red one intersecting the green one, then there's no way coordinate line A (I don't know the right term I could use to describe the line) has a natural number as its value (again I don't know how to say this in mathematical terms, as that would imply that there was a integer between two adjacent integers.

My question is: How could I put this into words?

My progress so far

Suppose there are 2 dyadic squares A, B of same size such that they are not the same, do not intersect along a common line or vertex. Let $M = \{x\in \mathbb{R}|x\in A \land x\in B\}$.

Since they intersect, they can intersect only in one of 2 possible ways (both drawn out below):

Let $x$ be any point in $M$. Consider the closest square side lying above $x$. This side is between two dyadic rationals, namely $\frac{a}{2^k}$ and $\frac{a+1}{2^k}$. This side lying between these two dyadic rationals would also be (by hypothesis) a dyadic rational (described in picture as $\frac{c}{2^k}$, implying that $\frac{a}{2^k} < \frac{c}{2^k} < \frac{a+1}{2^k}$, from which $a < c < a+1$ would follow, which is not possible for any $c\in \mathbb{Z}$

It is clear to me that there are some large gaps in this proof:

1. How could I show that the only way the two squares could intersect is in the ways I've drawn out below?

2. How could I show that it follows that there is a line lying above any point in the set M?

3. Overall, how do I make this proof more "mathematical"?

Lastly, I ask for some advice – I often catch myself having an idea such as this one but then greatly struggle with putting the proof together. How do I get better at this / practice this skill in a more targeted fashion?

Answer 1

It is notoriously difficult to translate/materialize visual understanding into rigorous mathematical reasoning. Through millions of years of evolution (or by God's design), we human beings have acquired amazing visual intelligence that far surpasses our capability of logical reasoning.

---

Back to this particular problem.

The trick here is to analyze dimension by dimension. Or, analyze the simpler case, dyadic intervals first and fully. Even though you can "see" the case of dyadic squares clearly does not mean it should be easy to prove the case of 2-dimension directly, as you have experienced. Always, always, always try to investigate a simpler case first. (Did I say always three times? Yes, I did.)

Suppose we have two dyadic intervals of same size, $[\frac{a}{2^k}, \frac{a+1}{2^k}]$ and $[\frac{b}{2^k}, \frac{b+1}{2^k}]$. These two intervals

• are the same if $a=b$,
• share an endpoint and no more if $|a-b|=1$,
• disjoint otherwise. (Do we need a proof here? Here it is anyway. We have $|a-b|>1$. WLOG, suppose $a<b$. Then $a+1<b$. $\frac{a+1}{2^k}<\frac b{2^k}$, which means the two intervals are disjoint.)

Now let us check two dyadic squares of same size, i.e., $I_1\times I_2$ and $J_1\times J_2$, where $I_1, I_2, J_1, J_2$ are dyadic intervals of same size. Thanks to our classification above of two dyadic intervals of same size, we can split the cases of two dyadic squares of same size into 4 disjoint cases below. Note that $$(I_1\times I_2)\cap (J_1\times J_2)=(I_1\cap J_1)\times(I_2\cap J_2).$$

• If $I_1$ and $J_1$ are disjoint or $I_2$ and $J_2$ are disjoint, the two squares are disjoint.
• If $I_1=J_1$ and $I_2=J_2$, the two squares are the same.
• If $I_1$ and $J_1$ share only an endpoint $x$ and $I_2$ and $J_2$ share only an endpoint $y$, the two squares shares only a vertex, $(x,y)$.
• The remaining cases are
  • when $I_1=J_1$ and $I_2$ and $J_2$ share only an endpoint $y$. Then the two squares shares a common edge, $I_1\times y$.
  • when $I_2=J_2$ and $I_1$ and $J_1$ share only an endpoint $x$. Then the two squares shares a common edge, $x\times I_2$.

We are done proving.

You can see that the description of $1$-dimensional cases make it very easy to handle $2$-dimensional cases and, in fact, all higher-dimensional dyadic cubes.

---

I often catch myself having an idea such as this one but then greatly struggle with putting the proof together.

It is a common situation. It happens to people (including me of course) numerous times and constantly.

How do I get better at this / practice this skill in a more targeted fashion?

This is a huge topic. Here is a very brief reply.

You are doing very well. Keep practice. Learn techniques, terminologies, conventions, etc. from examples where people put clear and rigorous proof when it appears difficult for you.