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.

On high frequency trading

I have complained to my coworker a few times about how I don't think high frequency trading is socially efficient. The coworker didn't really empathize as he saw the benefit of additional liquidity and I didn't really have a strong rationale behind my complaints. I have been thinking more about this issue lately and I think now I have some arguments to support my feeling.

The inefficiency is that trading firms spend millions of dollars to reduce latency at the unit of milliseconds. This is a natural consequence of the nature of high frequency trading competition, just as price competition is a natural consequence of free market. When a supplier in free market reduces the price of its products, its loss from the competition transfers directly to the consumers and in fact the perfect competition that drives the price down to the marginal cost exhausts all mutually beneficial trades to reach a Pareto optimum. On the other hand, the cost incurred from latency competition does not benefit anyone, except for very marginal increase in liquidity (the real social benefit of HFT is liquidity in terms of ask-bid spread, not in latency). In short, all those millions of dollars spent by trading firms to cut down the latency is deadweight loss to the society. And since the latency can never reach a true zero, the arms race can continue on and on. My guess is that at this very moment highly scarce human capital is spent on researching for reducing the trade latency.

I should mention that this is the same kind of social cost incurred by education signalling that I commented on last year. More precisely, it is a social cost of type of competition that has no counter party benefiting from the cost of competition. This type of competition is of course nothing but a form of Prisoner's dilemma, where the player reaps a huge benefit as long as he spends a little more than everyone else. The unique Nash equilibrium in this case would be that everyone spends as much as the benefit which is the worst social outcome.

I can't think of any way to solve this problem. Setting some minimum latency would be an obvious solution but the cost of enforcing it would well exceed the benefit. An easier rule to enforce is no high frequency trading at all. Not to say that HFT is without its benefits, but perhaps it deserves a cost-benefit analysis.

On patent

The recent court battle between Apple and Samsung has stirred the economics community a little to discuss about the efficiency of patent law. Becker and Posner both show concern that the current patent system is excessive. Becker cites Arnold Plant (1934) who advocated the elimination of patent system, agreeing that Plant erred in the right direction. Still, Becker finds patent system still necessary, writing: Although ending the patent system is a clean solution to all the problems induced by modern patenting, it clearly is not desirable given the importance of industries like the pharmaceutical industry. Since this industry spends on average hundreds of millions of dollars bringing to market a successful drug, pharmaceutical companies would not invest such large sums without the protection of patents (or without other benefits).

And today, I came across an article by Jordan Weissman that cites a working paper by Boldrin and Levine that argues for abolishing the patent system entirely: the best solution is to abolish patents entirely through strong constitutional measures and to find other legislative instruments, less open to lobbying and rent-seeking, to foster innovation whenever there is clear evidence that laissez-faire under-supplies it. The base of the bold argument is that, although well-designed patent system would indeed spur innovations, such system cannot occur with the current political structure. This part of the argument (part 3) feels rather weak at the moment, but that is not unexpected from a working paper.

The paper reminded me of an article by Steven Johnson in Wired magazine (October 2012, "Inventors' Gold"). Focusing primarily on pharmaceutical industry, Johnson argues that the government should offer lump-sum payouts instead of granting patents. The benefit of this alternative is that it eliminates the externality of patent monopoly while still providing incentive for innovation (the lump-sum payment, or the prize, would constitute the "other benefits" Becker mentions). It further solves Plant's concern that, as Becker summarizes, patents distort innovations in favor of goods and processes that can be patented and away from innovations that cannot be patented. In similar vein, Johnson argues that the current patent system does not allow innovations in some of the most needed drugs, such as those for tropical disease.

The last point, of course, is arguable and is in fact one down side of lump sum prize compared to patent. The burden of measuring the value of innovation lies on the government with the lump sum prize, while it lies on the innovators with patent system. As we know, government has less incentive to make accurate estimate. Furthermore, the cost of wrong estimation transfers from the innovator to the taxpayers with the lump sum prize, which may be socially undesirable. Still, I find the alternative of lump sum prize quite attractive over the current patent system.

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 Basic Ricardian Model

Given that Ricardian insight of comparative advantage is introduced in the very introductory economics classes and that the model is introduced quite early in the intro microeconomics, one would expect that I should know at least the simple Ricardian model inside out. Well, sadly this is not the case; I find going over the model in detail surprisingly nontrivial. In this post I am going to outline the basic Ricardian trade model.

Set Up

In the simple Ricardian model, there are two countries, home and foreign. It seems a literature tradition to postfix foreign variables with ^* so I will follow the tradition. There are two goods, 1 and 2, and single production factor, labor (L). The total labor endowments, L and L^*, are exogenously fixed (immobile across countries). Within each country, labor is perfectly mobile between the industries for good 1 and 2 (L₁ + L₂ = L).

The production function has constant returns to scale with marginal product of labor equal to a_i at home and a_i^* for i = 1, 2. In other words, to produce one unit of good 1 at home, it takes 1/a₁ units of labor, etc. As discussed earlier, CRS with single factor implies that the production function is linear: Q_i(L) = a_iL.

At this point we can find the production-possibility frontier: {(Q₁, Q₂) s.t. Q₁ = a₁L₁, Q₂ = a₂L₂, and L₁ + L₂ = L} = {(Q₁, Q₂) s.t. Q₁/a₁ + Q₂/a₂ = L}. Graphed on Q1-Q2 plane, the PPF is a straight line with slope -a₂/a₁.

Autarky Equilibrium

Let's consider the autarky equilibrium. Let p_i denote price in each industry and let p = p₁/p₂ be the relative price (of good 1). The model assumes perfect competition, so each industry makes zero profit: Π_i = p_iQ_i - w_iL_i = 0, where w_i denotes the wage for industry i. Solving for the wage, we get w_i = p_iQ_i/L_i = p_ia_i.

Suppose consumer preference is such that at any price both goods are demanded. For both goods to be produced, we require w₁ = w₂, implying p = a₂/a₁. We cannot determine the exact autarky equilibrium without a specific demand function, but we know it lies on some interior point of the PPF found above.

Trade Equilibrium

Allow the countries to trade with each other. Assume the foreign country has a comparative advantage in good 2. That is, a₂/a₁ < a₂^*/a₁^*, implying that home autarky relative price of good 1 is lower than the foreign's: p_a < p_a^*. To find the equilibrium price with trade, we consider the supply and demand as usual.

The world relative supply (of good 1) is 0 when both countries specialize in good 2. This occurs when the world relative price p is less than both the home and foreign autarky relative prices. On the other hand, both countries specialize in good 1 when p is greater than both of the autarky prices. If the world price lies strictly in between the autarky prices, so that p_a < p < p_a^*, then home specializes in good 1 while the foreign country specializes in good 2. The relative supply in this region is then (La₁)/(L^*a₂^*).

There are end points to consider. When p = p_a, the home country may produce both goods while the foreign country specializes in good 2, so that the world relative supply is less than or equal to (La₁)/(L^*a₂^*). When p = p_a^*, the foreign country may produce both goods while the home country specializes in good 1, so that the supply is greater than or equal to (La₁)/(L^*a₂^*).

Assuming identical and homothetic tastes across the countries so that the relative demand is decreasing in the relative price p, there are three possible cases. The equilibrium price may equal to the home autarky price or the foreign autarky price, or it my lie in between. Let's focus on the last case in which both countries specialize. Consider the new PPF of the home country. Since it specializes in good 1, it has total income of p₁a₁L. So the new PPF is {(Q₁, Q₂) s.t. p₁Q₁ + p₂Q₂ = p₁a₁L} = {(Q₁, Q₂) s.t. Q₁/a₁ + (1/p)Q₂/a₁ = L}. Since 1/p < 1/p_a = a₁/a₂, it follows that the old PPF is a proper subset of the new subset (and since we assumed the preference is such that both goods are demanded, the home country is strictly better off). Graphically, the PPF pivots outward centered at (La₁, 0) since the slope of the curve is now p > p_a. Similarly, for the foreign country which specializes in good 2, the PPF includes the end point (0, L^*a₂^*) but now has the slope of p < p_a^* so again it pivots outward.

So in the trade equilibrium, both countries are better off than in autarky. The Econ 101 punchline of the Ricardian model: mutually beneficial trade occurs when there exists a comparative advantage and the direction of the comparative advantage determines the specialization and direction of the trade. In particular, even if a country has no absolute advantage in either good, mutually beneficial trade occurs. For example, even if a₁ < a₁^* and a₂ < a₂^*, comparative advantage can lead to a trade (of course, if one country has a comparative advantage in one good, the other country has the advantage in the other good; if there is no comparative advantage, then autarky prices of both countries are the same, so there will be no gain from trading). How can the home country export when it has lower MPL for both goods?

The answer is that the wages are adjusting to the productivity. In the home country (specializing in good 1), the wage level is w = p₁a₁ and in the foreign country, it is w^* = p₂a₂^* > p₁a₁^* since p = p₁/p₂ < a₂^*/a₁^* = p_a^*. So a₁ < a₁^* implies w < w^*.

It is tempting to close the model with such an optimistic and insightful conclusion, but we have not finished examining the model since we have skipped the end point cases. The only thing to note here is that in the case both countries specialize, we can determine the relative output (La₁)/(L^*a₂^*) and use this to determine the equilibrium price given the demand (without demand specified, we can only put a bound). In the case only one country fully specializes, we know the price (the autarky price of the other country) but we have to determine the quantity from a specific demand function from the price. The point is, the model is analytically rather cumbersome even at the basic setting.

Thus the post-Ricardian models have focused on expanding the model to allow multiple countries and factors for empirical studies. Indeed, many international trade models seem to be characterized by three parameters: the number of countries, the number of industries, and the number of factors. Other than those, the most important part of Ricardian model would be the technological difference across countries, which allows gain from trade.

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.

Circular shift

I am going through the book Algorithms by Sedgewick and Wayne and found this interesting problem:

A string s is a circular rotation of a string t if it matches when the characters are circularly shifted by any number of positions; e.g., ACTGACG is a circular shift of TGACGAC, and vice versa. Detecting this condition is important in the study of genomic sequences. Write a program that checks whether two given strings s and t are circular shifts of one another.

Claim: strings t and s are circular shifts if and only if t and s have the same length and s is a substring of t + t, where + indicates string concatenation.

One direction is easy to show. Suppose t and s are circular shifts. By definition of circular rotation t and s are of the same length. Also by definition, there exist substrings u and v of t such that t = u + v and s = v + u. Therefore, t + t = u + v + u + v = u + s + v, so s is a substring of t + t.

Conversely, suppose t and s are strings of the same length N and that s is a substring of t + t. Thus, there exist substrings u and v such that t + t = u + s + v. Since t + t is of length 2N and s is of length N, u + v is of length N. Suppose u is of length m. Clearly, u is first m letters of t and v is last N - m letters of t. This implies t = u + v. It follows that t + t = u + v + u + v = u + s + v and thus s = v + u.

With the claim, the implementation is simple. In Java:

public static boolean circularshift(String t, String s)
{
  return t.length() == s.length() && (t + t).indexOf(s) != -1;
}

Any dutch-pay app?

I can't find any smartphone app that does this:

1. The user takes a photo of a restaurant receipt
2. The app performs OCR and makes a 3-column table
3. Column 1 contains the name of the item; column 2 contains the price of the item
4. For each item, the user inputs a set of ids of people (name, number, etc) on column 3
5. The app calculates the tax rate based on the total tax
6. The user inputs either total tips amount or tips percent
7. The app gives the total amount each person needs to pay including tax and tips

Efficient Grade Allocation

Economic efficiency is marked by allocation of a good to a person who value the good the most. One mechanism to find who has the highest value is to assign the object to the person who is willing to (and will) pay the most. Yet, not all scarce resource can be sold for money.

Suppose an instructor has given out grades for a class and everyone has already seen their grades. Before she submit the grades, however, the instructor is willing to increase the letter grade of exactly one student. Whose grade should she increase so that it is economically efficient? That is, how can she find the student who value the improved grade the most while minimizing the negative externality?