On square roots of non-perfect-squares being irrational

I started reading baby Rudin for my commute recently and was intrigued by the fact that he proves square root of 2 is irrational then gives as an exercise to prove square root of 12 is irrational. Well, why not just prove that a square root of any non-perfect-square is irrational?

I must admit I couldn't finish the proof in my head on the way to work. It took the return trip to convince myself that I had a proof. So the problem is not as trivial as it seems after all.

Let N be a non-perfect-square number. Suppose there exist a rational number n/m such that (n/m)² = N. In particular, such a rational number can be expressed in reduced terms so that gcd(n,m) = 1, so suppose that too. Let's start by noting that since N is not a perfect square, its prime factorization must have at least one prime number whose power is odd. Let this prime number be p, so that N = p^kq for some odd integer k and some integer q whose prime factorization does not have p.

That means (n/m)² = p^kq, or equivalently, n² = p^kqm². Thus p^k divides n². This implies p^k divides n, since the set of integers is a unique factorization domain (if the prime factorization of n had j≠k as the power for p, then the prime factorization of n² would have 2j as the power for p, but k is odd). So we can write n = p^kr for some integer r, and n² = p^2kr² = p^kqm². Therefore, p^kr² = qm².

Remember that q was the prime factorization of N sans p^k. So p^k must divide m². Again this implies p^k divides m, but this contradicts our assumption gcd(n,m) = 1.

Homogeneous production and average cost

I have discussed before that constant returns to scale (CRS) function with a single factor is of the form F(x) = cx where c is a constant. In this post, I wanted to show that if the two−factor production function has CRS, then the average cost is independent of the output level. Then I decided that such a result is too boring to deserve a post, so I am going to discuss the relationship between homogeneity of production function and average cost in full generality, following Sandmo (1970).

A function F: Rⁿ → R is homogeneous of degree k if a^kF(x) = F(ax) for all a > 0 and x in Rⁿ. A production function has constant returns to scale if it is homogeneous of degree 1. It has increasing returns to scale if homogeneous of degree k > 1, and decreasing returns to scale if homogeneous of degree k < 1. These properties can be defined locally (that is, find k as a function of x) by taking the derivative of the identity equation above with respect to a and then solving for k (assuming F is differentiable): ka^k−1F(x) = Σ F_ix_i and since a^k−1F(x) = F(ax)/a, we get k = aΣ (F_ix_i/F(ax)). Evaluating at a = 1, k = Σ (F_ix_i/F(x)).

Assume perfect competition in factor markets so that the factor prices are exogenously determined. Let r_i be the price of factor i and let r be the vector of prices. The total cost is then Σ r_ix_i. For fixed output level Q, the firm is cost minimizing with regard to x subject to its production function F(x) = Q. The Lagrangian is L = Σ r_ix_i − λ(F(x) − Q) and the first order conditions are r_i − λF_i = 0 for i = 1,..., n and F(x) − Q = 0. These n+1 equations yield the optimal x* as a function of r and Q and we can find the optimal cost C as a function of r and Q: C(r,Q) = Σ r_ix_i*.

While we are talking about cost function, let's mention that the Lagrange multiplier in cost minimization problem can be interpreted as the marginal cost. The derivative of this minimum cost function with regard to Q then is the marginal cost: dC/dQ = Σ r_i(dx_i*/dQ). By the first order conditions, r_i = λF_i. Totally differentiating F(x) = Q condition, we get Σ F_i(dx_i*/dQ) = 1. Thus, λ = dC/dQ.

Going back to the average cost problem, let A(r,Q) = C(r,Q)/Q be the average cost. To show the behavior of average cost as Q varies, take dA/dQ = Q⁻²(dC/dQ × Q − C). Thus the direction of average cost in Q depends on the sign of dC/dQ × Q − C or dC/dQ − C/Q. We showed C = Σ r_ix_i = λΣ F_ix_i and λ = dC/dQ. By the constraint, Q = F(x). Thus dC/dQ − C/Q = λ(1 − Σ (F_ix_i/F(x))). But we have also shown that k = Σ (F_ix_i/F(x)). Therefore, the average cost is increasing in Q if k > 1 (decreasing returns to scale), decreasing in Q if k < 1 (increasing returns to scale), and constant in Q if k = 1 (CRS).

The Envelope Theorem

I learned in school the Kuhn-Tucker conditions and the envelope theorem but I always felt I didn't have a complete understanding of them. One thing confusing about the envelope theorem is that there are different varieties of it, depending on the flavor of the optimization problem. I decided to review envelope theorem today and keep the notes in the blog.

Consider a constrained optimization problem on the function f(x,a) with regard to x subject to a g(x,a) = 0, where x is an n-vector and a is a scalar. Let M(a) be the solution to the problem; that is,

M(a) = max_x f(x,a) s.t. g(x,a) = 0.

The Lagrangian is then L = f(x,a) − λg(x,a), giving n+1 first-order conditions (or, n first-order conditions and m complementary slackness conditions for more general constrained optimization problem with m inequality constraints). These conditions yield the optimizing argument x*(a) and the solution M(a) = f(x*(a), a).

The envelope theorem states that if x*(a) is a C¹ function and the usual constraint qualification is satisfied (∇g(x*(a))≠0), then M'(a) = ∂L(x,a)/∂a evaluated at x = x*(a). To put crudely, to differentiate the solution with regard to a parameter (say for comparative statics), one only needs to differentiate the Lagrangian with respect to the parameter and then "plug in" the solution x* rather than explicitly find M(a) and then differentiate it.

The proof for this version of envelope theorem is a straight-forward calculation. Since M(a) = f(x*(a), a), it follows

M'(a) = Σ(∂f/∂x_i)(∂x_i/∂a) + ∂f/∂a

for i = 1,..., n.

By the first order conditions, ∂f/∂x_i = λ∂g/∂x_i for each i. It follows

M'(a) = λ Σ(∂g/∂x_i)(∂x_i/∂a) + ∂f/∂a

Identically, it must be that g(x*(a), a) = 0. Differentiating this equality with respect to a yields Σ(∂g/∂x_i)(∂x_i/∂a) + ∂g/∂a = 0. So we get

M'(a) = -λ∂g/∂a + ∂f/∂a evaluated at x = x*(a).

But of course, -λ∂g/∂a + ∂f/∂a = ∂L/∂a

The more general case with m inequality constraints have a similar flavor of proof: differentiate the maximum function with respect to the parameter, collect the terms, and then use the first order conditions and complementary slackness conditions to cancel out the terms. The theorem can be further generalized into the case in which the parameter is a k-vector rather than a scalar.

CRS function with single factor

An assumption of Ricardian model is constant returns to scale production function with single production factor (labor). Therefore, the marginal product of labor (or, in the usual manner of presentation, its inverse, the units of labor required to produce one unit of good) completely describes the production function. This was so intuitively clear that I never bothered to check.

A production function F(x): Rⁿ → R has constant returns to scale if F(ax) = aF(x) for all a > 0, where x is a n-vector and a is a scalar. In other words, it's economists' way of saying degree 1 homogeneous.

The claim is that if n = 1, then F(x) = cx for some real number c. The proof is simple. Suppose F has constant returns to scale, and denote F(1) = c. Then ac = aF(1) = F(a) for all a > 0. F(0) = 0 follows from the observation that F(0) = aF(0) for all a > 0. Finally, since F(1) = -F(-1), it follows -ac = aF(-1) = F(-a) for all a > 0.

Of course, I could have used Euler's theorem which states that F(x) is homogeneous of degree k iff nF(x) = Σ_ix_iF_i where F_i is partial derivative of F regard to x_i. Thus, single factor CRS function satisfies F(x) = xF'(x). Solving differential equation yields F(x) = cx.