text:
# Understanding the Matched Filter

I have a question about matched filtering. Does the matched filter maximise the SNR at the moment of decision only? As far as I understand, if you put, say, NRZ through a matched filter, the SNR will be maximised at the decision point only and that is the advantage of the matched filter. Does it maximise the SNR anywhere else in the output function, or just at the point of decision?

According to Wikipedia

The matched filter is the optimal linear filter for maximizing the signal to noise ratio (SNR) in the presence of additive stochastic noise

This to me implies that it maximises it everywhere, but I don't see how that is possible. I've looked at the maths in my communications engineering textbooks, and from what I can tell, it's just at the decision point.

Another question I have is, why not make a filter that makes a really tall skinny spike at the point of decision. Wouldn't that make the SNR even better?

Thanks.

Edit: I guess what I'm also thinking is, say you have a some NRZ data and you use a matched filter, the matched filter could be implemented with an I&D (integrate and dump). The I&D will basically ramp up until it gets to the sampling time and the idea is that one samples at the peak of the I&D because at that point, the SNR is a maximum. What I don't get is, why not create a filter that double integrates it or something like that, that way, you'd have a squared increase (rather than a ramp) and the point at which you sample would be even higher up and from what I can tell, more likely to be interpreted correctly by the decision circuit (and give a lower Pe (probability of error))?

• Read this answer and specifically the link in the last sentence. Your double integration is effectively computing the output (at the desired sampling time) of a non-matched filter and so cannot give a smaller $P_e$ than the matched filter if the noise is additive Gaussian. If the noise is additive Gaussian noise, then no filter, whether linear or nonlinear, can give a smaller error probability than the matched filter. – Dilip Sarwate May 12 '13 at 15:11

Since this question has multiple sub-questions in edits, comments on answers, etc., and these have not been addressed, here goes.

Matched filters

Consider a finite-energy signal $s(t)$ that is the input to a (linear time-invariant BIBO-stable) filter with impulse response $h(t)$, transfer function $H(f)$, and produces the output signal $$y(\tau) = \int_{-\infty}^\infty s(\tau-t)h(t)\,\mathrm dt.\tag{1}$$ What choice of $h(t)$ will produce a maximum response at a given time $t_0$? That is, we are looking for a filter such that the global maximum of $y(\tau)$ occurs at $t_0$. This really is a very loosely phrased (and really unanswerable) question because clearly the filter with impulse response $2h(t)$ will have larger response than the filter with impulse response $h(t)$, and so there is no such thing as the filter that maximizes the response. So, rather than compare apples and oranges, let us include the constraint that we seek the filter that maximizes $y(t_0)$ subject to the impulse response having a fixed energy, for example, subject to $$\int_{-\infty}^\infty |h(t)|^2\,\mathrm dt = \mathbb E = \int_{-\infty}^\infty |s(t)|^2 \,\mathrm dt.\tag{2}$$

Here onwards, "filter" shall mean a linear time-invariant filter whose impulse response satisfies (2).

The Cauchy-Schwarz inequality provides an answer to this question. We have $$y(t_0) = \int_{-\infty}^\infty s(t_0-t)h(t)\,\mathrm dt \leq \sqrt{\int_{-\infty}^\infty |s(t_0-t)|^2 \,\mathrm dt} \sqrt{\int_{-\infty}^\infty |h(t)|^2\,\mathrm dt} = \mathbb E$$ with equality occurring if $h(t) = \lambda s(t_0-t)$ with $\lambda > 0$ where from (2) we get that $\lambda = 1$, that is, the filter with impulse response $h(t) = s(t_0-t)$ produces the maximal response $y(t_0) = \mathbb E$ at the specified time $t_0$. In the (non-stochastic) sense described above, this filter is said to be

the filter matched to $s(t)$ at time $t_0$ or the matched filter for $s(t)$ at time $t_0.$

1. The output of the matched filter has a unique global maximum value of $\mathbb E$ at $t_0$; for any other $t$, we have $y(t) < y(t_0) = \mathbb E$.

2. The impulse response $s(t_0-t) = s(-(t-t_0))$ of the matched filter for time $t_0$ is just $s(t)$ "reversed in time" and moved to the right by $t_0$.

a. If $s(t)$ has finite support, say, $[0,T]$, then the matched filter is noncausal if $t_0 < T$.

b. The filter matched to $s(t)$ at time $t_1 > t_0$ is just the filter matched at time $t_0$ with an additional delay of $t_1-t_0$. For this reason, some people call the filter with impulse response $s(-t)$, (that is, the filter matched to $s(t)$ at $t=0$) the matched filter for $s(t)$ with the understanding that the exact time of match can be incorporated into the discussion as and when needed. If $s(t) = 0$ for $t < 0$, then the matched filter is noncausal. With this, we can rephrase 1. as

3. The matched filter for $s(t)$ produces a unique global maximum value $y(0) = \mathbb E$ at time $t=0$. Furthermore, $$y(t) = \int_{-\infty}^\infty s(t-\tau)s(-\tau)\,\mathrm d\tau = \int_{-\infty}^\infty s(\tau-t)s(\tau)\,\mathrm d\tau = R_s(t)$$ is the autocorrelation function of the signal $s(t)$. It is well-known, of course, that $R_s(t)$ is an even function of $t$ with a unique peak at the origin. Note that the output of the filter matched at time $t_0$ is just $R_s(t-t_0)$, the autocorrelation function delayed to peak at time $t_0$.

4. No filter other than the matched filter for time $t_0$ can produce an output as large as $\mathbb E$ at $t_0$. However, for any $t_0$, it is possible to find filters that have outputs that exceed $R_s(t_0)$ at $t_0$. Note that $R_s(t_0) < \mathbb E$.

5. The transfer function of the matched filter is $H(f)=S^*(f)$, the complex conjugate of the spectrum of $S(f)$. Thus, $Y(f) = \mathfrak F[y(t)]= |S(f)|^2$. Think of this result as follows. Since $x^2 > x$ for $x > 1$ and $x^2< x$ for $0 < x < 1$, the matched filter has low gain at those frequencies where $S(f)$ is small, and high gain at those frequencies where $S(f)$ is large. Thus, the matched filter is reducing the weak spectral components and enhancing the strong spectral components in $S(f)$. (It is also doing phase compensation to adjust all the "sinusoids" so that they all peak at $t=0$).

## -------

But what about noise and SNR and stuff like that which is what the OP was asking about?

If the signal $s(t)$ plus additive white Gaussian noise with two-sided power spectral density $\frac{N_0}{2}$ is processed through a filter with impulse response $h(t)$, then the output noise process is a zero-mean stationary Gaussian process with autocorrelation function $\frac{N_0}{2}R_s(t)$. Thus, the variance is $$\sigma^2 = \frac{N_0}{2} R_s(0) = \frac{N_0}{2}\int_{-\infty}^{\infty} |h(t)|^2\,\mathrm dt.$$ It is important to note that the variance is the same regardless of when we sample the filter output. So, what choice of $h(t)$ will maximize the SNR $y(t_0)/\sigma$ at time $t_0$? Well, from the Cauchy-Schwarz inequality, we have $$\text{SNR} = \frac{y(t_0)}{\sigma} = \frac{\int_{-\infty}^\infty s(t_0-t)h(t)\,\mathrm dt}{\sqrt{\frac{N_0}{2}\int_{-\infty}^\infty |h(t)|^2\,\mathrm dt}} \leq \frac{\sqrt{\int_{-\infty}^\infty |s(t_0-t)|^2 \,\mathrm dt} \sqrt{\int_{-\infty}^\infty |h(t)|^2\,\mathrm dt}}{\sqrt{\frac{N_0}{2}\int_{-\infty}^\infty |h(t)|^2\,\mathrm dt}} = \sqrt{\frac{2\mathbb E}{N_0}}$$ with equality exactly when $h(t) = s(t_0-t)$, the filter that is matched to $s(t)$ at time $t_0$!! Note that $\sigma^2 = \mathbb EN_0/2$. If we use this matched filter for our desired sample time, then at other times $t_1$, the SNR will be $y(t_1)/\sigma < y(t_0)/\sigma = \sqrt{\frac{2\mathbb E}{N_0}}$. Could another filter give a larger SNR at time $t_1$? Sure, because $\sigma$ is the same for all filters under consideration, and we have noted above that it is possible to have a signal output larger than $y(t_1)$ at time $t_1$ by use of a different non-matched filter.

In short,

• "does the matched filter maximize the SNR only at the sampling instant, or everywhere?" has the answer that the SNR is maximized only at the sampling instant $t_0$. At other times, other filters could give a larger SNR than what the matched filter is providing at time $t_1$, but this still smaller than the SNR $\sqrt{\frac{2\mathbb E}{N_0}}$ that the matched filter is giving you at $t_0$, and if desired, the matched filter could be redesigned to produce its peak at time $t_1$ instead of $t_0$.

• "why not make a filter that makes a really tall skinny spike at the point of decision. Wouldn't that make the SNR even better?"
The matched filter does produce a spike of sorts at the sampling time but it is constrained by the shape of the autocorrelation function. Any other filter that you can devise to produce a tall skinny (time-domain) spike is not a matched filter and so will not give you the largest possible SNR. Note that increasing the amplitude of the filter impulse response (or using a time-varying filter that boosts the gain at the time of sampling) does not change the SNR since both the signal and the noise standard deviation increase proportionately.

• "The I&D will basically ramp up until it gets to the sampling time and the idea is that one samples at the peak of the I&D because at that point, the SNR is a maximum."
For NRZ data and rectangular pulses, the matched filter impulse response is also a rectangular pulse. The integrate-and-dump circuit is a correlator whose output equals the matched filter output only at the sampling instants, and not in-between. See the figure below.

If you sample the correlator output at other times, you get noise with smaller variance but you can't simply add up the samples of I&D output taken at different times because the noise variables are highly correlated, and the net variance works out to be much larger. Nor should you expect to be able to take multiple samples from the matched filter output and combine them in any way to get a better SNR. It doesn't work. What you have in effect is a different filter, and you cannot do better than the (linear) matched filter in Gaussian noise; no nonlinear processing will give a smaller error probability than the matched fiter.

• Great answer. There's a significant portion of a digital communication theory course shoved into one package. – Jason R Jun 2 '13 at 12:39
• Thank you for the great answer! I have a question regarding the graph of the matched filter output. What's the output of that graph (I'm trying to hand draw it)? I'm assuming that it's $y(t) = r(t) * r(-t)$ where $y(t)$ is the output signal (third graph) and $r(t)$ is the received signal (first graph). If I correlate the received signal with a box function tall enough to pass encompass both the logic level 1 and 0 states, then I get that output---the only thing is, there is never a 100% match between the correlated signal and the correlation signal, perhaps that is to be expected. – user968243 Jun 7 '13 at 6:46
• With $p(t)$ denoting a rectangular pulse lasting from $0$ to $T$, the received signal is $r(t)=\sum_{n=0}^\infty (-1)^{b_n}p(t-nT)$, the matched filter has impulse response $h(t)=p(-t)$ and the filter output is $$(r\star h)(t)=\int_{-\infty}^\infty r(u)h(t-u)\,du=\int_{-\infty}^\infty r(u)p(u-t)\,du=\int_{t-T}^t r(u)\,du,$$ that is, the matched filter output at any time $t$ is the integral of the received signal (plus noise, of course) over the past $T$ seconds. Note that except at the sampling instants, the filter output has receiver-induced intersymbol interference (ISI) in it! (continued) – Dilip Sarwate Jun 7 '13 at 10:57
• (continued) This ISI is another reason why your idea of taking multiple samples from the matched filter output and then processing them somehow to improve SNR will not work as well as you think it might. – Dilip Sarwate Jun 7 '13 at 10:59
• Okay thanks! It seems to me, though, that the matched filter really is a correlator... It's just that the correlator in graph two is really implemented as an integrator that needs to restart integrating every T in order to look like a correlator at T. Seems to me that the matched filter is more like a correlator than the correlator (I know that sounds odd). – user968243 Jun 7 '13 at 12:11

You are right: A matched filter will maximize SNR at the instant of decision.

Note that your proposal of a tall spike "filter" is not a filter, but actually a sampler (the sampler used at the decision point).

The matched filter is a filter (i.e. linear time-invariant system) applied to the continuous input signal. The "spike at the point of decision" is very time-dependant (it is not a filter but a sampler).

• I've added an edit to my question. I tried to post it in the comments here but it was too long and not allowed. Thanks for your answer. – user968243 May 12 '13 at 4:39

The matched filter is the maximum-likelihood receiver in the presence of additive white Gaussian noise. Thus, for equal prior symbol probabilities, it will yield optimum bit-error performance. This is equivalent on the AWGN channel to maximizing the signal-to-noise ratio, as you pointed out. You also correctly pointed out that this maximum-SNR condition is at the decision instant for each symbol.

The misconception in your proposal is that you can't do any better than the matched-filter approach on the AWGN channel. The output of the filter for time instants other than the decision point is irrelevant for bit-error performance. In a practical sense, it can be easier to obtain symbol-timing synchronization if the matched-filter output (i.e. the shape of the autocorrelation of the signal's pulse shape) has an impulse-like shape. In fact, some real communication techniques (like direct sequence spread spectrum modulation) have this property.

Assuming perfect synchronization, however, which is the typical case when analyzing bit-error rates, the performance that is attained is unrelated to the shape of the matched filter's output; all that matters is the total energy in the pulse, which determines the value of the matched filter's output at the decision point.

Furthermore, it can be very difficult to design a different filter that would have the specific time-domain response that you want. Such a process is known as deconvolution, and isn't easy. The double-filter approach that you suggest would actually have the opposite effect of smearing out the decision statistic even further (convolution inherently smears the signal out in time). You could perhaps devise some nonlinear filter that would give you a shape that you like more, but it isn't clear that it would retain the optimality of the matched filter approach.

• Okay, thanks for the reply. You said that the output of the matched filter not at the decision point make no difference and are irrelevant. I had figured this out and was wondering why a better filter could not be made, say, one that grabs the energy contained in those portions and includes that at the point of decision. Not sure if that makes sense! Hope it does! My guess is that this can't be done because then the filter wouldn't be linear... – user968243 May 12 '13 at 16:50

I cannot answer your question in theory, however I can answer it practically - You may see it using a matched filter simulator (http://www.grauonline.de/alexwww/ardumower/filter/filter.html).

All the above answers nicely describe how matched filter is optimal but do not discuss why other samples are useless as far as decision is concerned. The interesting perspective on these non-optimal samples comes from taking a frequency domain view.

Remember that cross-correlation in time domain is conjugate multiplication in frequency domain. When sampled at the optimal instant, the phases of all frequency bins are aligned such that the energy is maximized in I branch of the result and there is no Q arm. When sampled at another instant, phase rotations are introduced due to this time shift difference which are different for each frequency bin. See the figure below.

Moreover, the noise samples, having passed through the matched filter, become correlated. This correlation is zero only when matched filter output crosses zeros, i.e., optimal sampling instants.

It is explained in much more detail in the article on demodulation.

Sometimes it is more useful to have a filter with a small tiny spike in the middle like you said. One such filter is called the MACE filter. This is the original paper

Mahalanobis, A., Kumar, B.V.K.V., Casasent, D.: Minimum average correlation energy ﬁlters. Appl. Opt. 26, 3630–3633 (1987)


text:
# [Cvsnt] "RespositoryPrefix" key

Bertrand Denoix bertrand.denoix at kalimagroup.com
Wed Dec 5 17:31:13 GMT 2001

Community technical support mailing list was retired 2010 and replaced with a professional technical support team. For assistance please contact: Pre-sales Technical support via email to sales@march-hare.com.

A recent post in the listed hinted that instead of defining several
repositories with keys:

Repository0=d:\some\long\path\to\first_repository
Repository1=d:\some\long\path\to\second_repository

I could use something like:

RepositoryPrefix=d:\some\long\path\to\
Repository0=first_repository
Repository1=second_repository

Is this really possible? (if not skip the rest :-)

What is the real syntax?

My 1.11.1.2 (Build 40) doesn't mention this anywhere (readme.nt or the
cvsservice dialog), but I didn't see it mentioned by Tony in the
archives (esp when expounding the new things in 1.11.1.3).
Since when is it available?

Does that mean that users CVSROOT changes from

:ntserver:my_server:d:\some\long\path\to\first_repository

to a simpler:

:ntserver:my_server:first_repository

Thanks for a quick answer because we are adding a bunch of new users in
the coming days and that would make things simpler for them (even
simpler if we change the setup before they use it).

Bd.

_______________________________________________
Cvsnt mailing list
Cvsnt at cvsnt.org
http://www.cvsnt.org/cgi-bin/mailman/listinfo/cvsnt https://www.march-hare.com/cvspro/en.asp#downcvs

format: plain


text:
## Problem C. Cup and Championship ≡

 Author: I. Ludov Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

### Statement

The city of Kislodriftinsk holds two prestigious drifting contests with different rules.

The Kislodriftinsk Drifting Championship consists of head-to-head matches between all pairs of pilots. Judging rules exclude draws, so after every match exactly one participant receives one score point. The champion of Kislodriftinsk is determined as the pilot with maximum summary score (i. e. beating maximum number of other participants). Note that there may be several champions with equal scores.

The Kislodriftinsk Drifting Cup is conducted by olympic play-off system (aka single elimination). All participants are divided into pairs and winners of every pair are determined. Winners then make new pairs and the process is repeated until there is only one participant left, who becomes a cup winner.

Rising star of Kislodriftinsk motorsports, Kesha Tsuchiyev, has already became one of Championship winners this year and now wants to also win in the forthcoming Cup. His task is simplified by the fact that both contests have same set of participants and same judge teams. This implies that the result of every match in the Cup will be the same as in the Championship with the same pair of participants. Being one of Championship winners, Kesha will win a significant proportion of possible Cup matches.

However, Kesha suspects that in the case of unfortunate pair composition, he may not even advance to second stage, having lost the very first match. Your program must help him calculate any Cup schedule which leads him to victory, or determine that it is impossible.

### Input file format

Input file contains integers N T. Following N lines contain N integers each — a matrix of head-to-head matches results. A number in row i and column j is equal 1 if i-th pilot wins against j-th and 0 otherwise. Diagonal contains zeroes. Kesha Tsuchiyev is a pilot number T, numbers start from zero.

### Output file format

Output file must contain N integers s0,i which is a permutation of pilot numbers 0… N − 1 determining a schedule of play-off championship as follows: In the first round N / 2 matches are conducted between pairs (s0,0 vs s0,1), (s0,2 vs s0,3), etc. Winners of these matches form a sequence s1,i. Then the process is repeated, i.e. N / 4 matches are conducted between pairs (s1,0 vs s1,1), (s1,2 vs s1,3) etc. The winner of play-off cup is the only number left in the sequence sk,i for some k, and this number must be equal to T. If there is no solution, output file must contain a single integer 1.

### Constraints

2 ≤ N ≤ 64, N is a power of 2, 0 ≤ T < N

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 2
0 1 0 0
0 0 0 0
1 1 0 1
1 1 0 0
1 2 0 3
2
4 2
0 1 0 0
0 0 1 0
1 0 0 1
1 1 0 0
2 3 0 1

0.040s 0.008s 13


text:
## College Algebra (10th Edition)

Published by Pearson

# Chapter 1 - Review Exercises - Page 145: 13

#### Answer

No real solutions.

#### Work Step by Step

We solve: $x(x+1)+2=0$ $x^{2}+x+2=0$ We solve using the quadratic formula ($a=1,\ b=1,\ c=2$): $\displaystyle x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$ $\displaystyle x=\frac{-1\pm\sqrt{(1)^{2}-4*1*2}}{2(1)}=\frac{-1\pm\sqrt{-7}}{2}$ However, we note that the discriminant is negative. Therefore, there are no real solutions.

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.


text:
International
Tables for
Crystallography
Volume D
Physical properties of crystals
Edited by A. Authier

International Tables for Crystallography (2006). Vol. D, ch. 1.8, p. 220

Section 1.8.2. Macroscopic equations

G. D. Mahana*

aDepartment of Physics, 104 Davey Laboratory, Pennsylvania State University, University Park, Pennsylvania, USA
Correspondence e-mail: gmahan@psu.edu

1.8.2. Macroscopic equations

| top | pdf |

The basic equations of transport are given below (Ziman, 1962; Goldsmid, 1986; Mahan, 1990). (The symbols used in this chapter are defined in Section 1.8.6.) where and are the current density and the heat current, respectively. The three main transport coefficients are the electrical conductivity , the thermal conductivity K and the Seebeck coefficient S. The electrical resistivity is the inverse of the conductivity, . In general, the currents, electric field and are vectors while , S and are second-rank tensors. The number of independent tensor components is determined by the symmetry of the crystal (see Chapter 1.1 ). We assume cubic symmetry, so all of the quantities can be treated as scalars. Onsager relations require that the Seebeck coefficient S is the same in the two equations. A description of the transport properties of most crystals is simply given as a graph, or table, of how each of the three parameters varies with temperature. The range of variation among crystals is enormous.

The above equations assume that there is no magnetic field and have to be changed if a magnetic field is present. This special case is discussed below.

References

Goldsmid, H. J. (1986). Electronic refrigeration. London: Pion Limited.
Mahan, G. D. (1990). Many-particle physics, 2nd ed. New York: Plenum.
Ziman, J. M. (1962). Electrons and phonons. Oxford University Press.


text:
# Atmospheric humidity for water production.

Tags:
1. Mar 26, 2015

### RobertGC

*Suggestions for Water Production for California.*

California is still in the midst of a huge drought:

Annie Sneed Science 03.23.15 7:00 am
California’s About to Run Out of Water. We Have to Act Now.
http://www.wired.com/2015/03/californias-run-water-act-now/

There appear to be however relatively simple methods of providing extra water. One is by deriving water from humidity in the air, the other by distilling the water from the ocean. Both would appear to have relatively low cost solutions.

First the humidity solution. The amount of water in the form of water vapor is substantial, especially at high humidity. A key fact is air can store more water vapor at higher temperatures. But the point is the areas in California with the highest drought level are the areas with routine high temperatures, such as Los Angeles. So lets calculate the amount of water in air in Los Angeles. This page gives a graph of average relative humidity levels in LA:

Average Weather For Los Angeles, California, USA.
https://weatherspark.com/averages/30699/Los-Angeles-California-United-States

You see that the relative humidity commonly reaches the 80% range and above, especially during the warmer months. The relative humidity is the percentage of the maximum possible water vapor the air can hold based on that temperature, called the saturated vapor density. This page gives a calculator for the saturated vapor density based on temperature.

Relative Humidity Calculation.
http://hyperphysics.phy-astr.gsu.edu/hbase/kinetic/relhum.html

For a temperature of 80 degrees F, the saturated vapor density is given as 25.4 gm/m^3. And for a relative humidity of 80%, this corresponds to an actual amount of water in the air of 20.3 gm/m^3, 0.0203 kg/m^3.

*Residential Solutions.*

Some ceiling fans can move quite large amounts of air at a time resulting in quite large amounts of water vapor inflow at a time, if placed for example in residential windows. For instance some fans on this page at their higher speed settings can move 5,000 cubic feet per minute (CFM) of air while using only 30 watts:

ENERGY STAR Most Efficient 2015 — Ceiling Fans 52 inches and under.
http://www.energystar.gov/index.cfm?c=most_efficient.me_ceiling_fans_under_52_inches

Lower speeds give better energy efficiency, but at the cost of lowered air flow amounts. We’ll use the high speed numbers since we want large air flow to get high water vapor inflow.

At this high amount of hot air inflow though we would probably want the fan in a basement or attic since we would also need a window for the hot air, once the water is removed, to exit.

How much water would need to be produced? An average person uses about 50 gallons per day of water:

City Utilities: Water Tips.
http://www.cityutilities.net/resident/pgms/watertips.htm

So say a residence for a family of 4 needed 200 gallons of water per day. A gallon is 3.785 liters, so this is 757 liters per day. Water weighs 1 kilo per liter so this is 757 kilos per day. Then how long would it take for a fan blowing in 5,000 cubic feet per minute to bring in this much water(vapor)? At 5,000 cfm this is 5,000/3.28^3 = 141.7 meters per minute. Each of these cubic meters of air would contain 0.0203 kg of water vapor. So this would amount to 2.88 kg per minute of water. This would take 262.8 minutes, about 4.4 hours.
This amount of power, only 30 watts used for 4.4 hours, is also quite small in energy costs compared to what the county of Los Angeles charges for water.

An additional question to be resolved however is how can we convert this water vapor to liquid water? Air conditioners are able to do this, by accident, by chilling the air. Air dehumidifiers also commonly work this way. This causes water to condense out like happens for example in cool morning temperatures with morning dew. On our relative humidity calculator page, at 80 degrees F and 80% relative humidity, the dew point is only 73.4 F. However, both air conditioners and air humidifiers use quite high power levels. We want to minimize additional power used.

Some possibilities:

1.)If the water produced this way is an adjunct to the water received from the city, then we can use the cool water coming from the city water supply, typically around 50 degree F, to cool this air and get the water to condense out.

2.)It would be nice though, since the calculation showed this air-produced water alone is sufficient to supply the entire household water needs, to find a way that didn’t use the city water supply.

a.)Another type of air dehumidifier uses desiccants to absorb water vapor. The desiccant material is then heated to release the water as liquid and the same desiccant is used over again. However, this material typically is a silica compound and you would not want remnants of this to be left in the water. This also uses additional power for the heating step. If a desiccant could be found that is a type of mineral you would normally see for example in spring water then this might work. You would though need to find a way to get the water to be released as a liquid. Heating as with air dehumidifiers would work. However it may be at the high temperature of southern California would be sufficient so this would happen naturally.

b.) A similar possibility derives from the fact that rain droplets can frequently condense in the air out of water vapor at temperatures higher than they would normally do by having nucleation sites:

Cloud condensation nuclei.
http://en.wikipedia.org/wiki/Cloud_condensation_nuclei

Then we could add nucleators into the air stream to get the air to condense. These nucleators though again would have to be a non-toxic if ingested. Ideal would again be some type of mineral commonly found in mineral water.

c.)To get the water to condense we could also expand the air flow. Rapidly expanding the air would cause the temperature to drop thereby chilling the water. A problem here though is the air flow is so large it might require an unreasonable size of expansion needed to get the needed temperature drop.

d.)Another possibility would be by increasing the pressure of the air. Just as increasing the pressure increases the temperature at which water makes the transition from liquid to gas, the boiling point, so also the temperature at which it makes the transitions from gas to liquid, the dew point, also increases. This page gives a calculator for how the pressure changes the dew point:

Dew Point Conversion Calculator.
http://www.howelllabs.com/resources/dew-point-conversion-calculator/

Enter in 73.4 degrees F in the known dew point field for our 80 degree F and 80% relative humidity scenario. Enter in 0 for the “psig” field, which measures how far this is above standard pressure in psi. Then a psig of only 4 gives a dew point of 80.3 F. That is an increase in pressure of less than 30% results in the water condensing out.

We might be able to generate this amount of extra pressure by circulating the air around in a circle by centrifugal force. A problem though is the size of the air stream coming from a large ceiling fan size diameter might make the circle size needed impractically large. We could constrict the air coming from the fan into a smaller pipe diameter, but by the Bernoulli principle this would reduce the pressure. It still may be possible though that some combination of restricted pipe diameter and circulation diameter size could provide the needed pressure change at a practical size.

*Water Utility Solution.*

For the water company using this method to produce extra water it becomes particularly simple. The large ceiling-fan type fans discussed in the residential solution only move air in the range of 3 to 4 miles per hour. But wind speeds commonly are above this speed especially in coastal areas. Then you would not even need to use fans for the water utility solution. You would just collect the air driven by the wind in large tubes for processing. Also, for California communities near the coast, using the ocean to supply the necessary cooling to condense the water vapor becomes especially simple.

*Individual Water Production.*

For a scenario where one is stranded out in the wild or in a life raft without water, the amount of power needed for the fan is so small that it could probably be generated by hand for a single individual just for enough water to sustain life. And considering the wind speed needed is only in the range of 3 to 4 mph a fan might not be needed at all.
Also, at least for an 80 F and 80% relativity humidity scenario, the 30% extra pressure needed to allow water to condense could be easily supplied by hand. By the Ideal Gas Law PV = RT, to get a 30% increase in pressure we would need to make less than a 23% decrease in volume, assuming we did the compression slowly so as not to increase the temperature. For instance, a piston in a foot long cylinder would only need to make a 3 inch compression to get the needed pressure.
The life boat case would also be very simple because the condensing could instead be done by using the cool temperatures of the ocean water.

Bob Clark

2. Mar 26, 2015

### DaveC426913

Perhaps I am being naive but aren't your numbers for average humidity in the L.A. are based on normal weather cycles? If there is a drought, does it not mean that the amount of vapour in the air is substantially lower than that average?

3. Mar 26, 2015

### phyzguy

There's a lot of scare-mongering around the situation in California. Here are some things to remember:

* Household water users use less than 10% of California's water, so even if all of California's residents cut their water use to zero by the techniques you describe, it would only reduce the water usage by less than 10%, and the cost would be quite substantial. Also, even at the current levels of rainfall, there is more than enough water to supply all household water needs.

* Agriculture uses the majority of California's water. The value of most of the crops grown is simply not high enough to pay for desalination or condensing water out of the air. To give you some rough numbers, water from the huge Carlsbad desalination plant being built near San Diego will cost about $2000 per acre-foot of water ( an acre-foot of water is one acre covered to a depth of one foot, also 43,560 cubic feet, about 320,000 gallons or about 1.2 M liters). A crop like alfalfa, one of California's largest water users, needs something between 1-4 feet of water per year, depending on rainfall, so it would cost$2000-$8000 to water an acre of crop for a year. But an acre of alfalfa only produces on the order of$1000 worth of crop (depending on yield, prices, etc.). I'm being very rough, but the point is that there are very few if any agricultural crops that are worth enough to pay for the very expensive methods you propose. Remember that the agricultural industry in California has grown up with water provided from rivers and snow melt, which is very cheap (on the order of \$100 per acre-foot or less) compared to desalination or condensing water out of the air.

Many people may disagree, but I think the bottom line is that if the rains don't return, much of California's agriculture may have to be grown somewhere else. High value crops like fruits, nuts, and vegetables will probably continue to make sense, but low value crops like alfalfa, hay, and rice, which consume most of California's agricultural water today, may have to be grown elsewhere.

4. Mar 26, 2015

### Staff: Mentor

Welcome to PF, Robert.

While you stated a power input for bringing the air into the building (way too low, but at least you tried - ceiling fans do not bring air into a house), that's the easy part. Condensing the water vapor is what takes most of the energy. So you can't really know how much this is going to cost unless you do that calculation.


text:
# Can one use complex numbers in probability?

I have never thought about using complex numbers in probability. I am examining Bayes Theorem, and attempting to relate it to projective geometry and this question came to mind. I am not talking about probability amplitude or any application to quantuum theory. I am asking about pure math.

Could someone give a simple example where the answer to a question is eg 2+i?

-
In my opinion: It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. – Git Gud May 9 '13 at 22:20
The characteristic function $E(e^{it X})$ is useful. – André Nicolas May 9 '13 at 22:33
i may be asking a very stupid question… i tend to do this… so a simple pointer in the right direction would help... – happyseaurchin May 9 '13 at 22:46
Easy $1+i+1=2+i$ – TylerHG Jun 1 '14 at 2:29
This is not a stupid question (actually no question is stupid) since it can lead to either of 2 outcomes: 1. a correct answer and thus illumination or, 2. a breakthrough. And in this case there is such a formulation (which can be a breakthrough), see my answer – Nikos M. Jun 1 '14 at 2:38

It's not a stupid question, but it's not the sort of question that has an answer.

The big exciting thing that's going on with complex numbers and probability is Schramm Lowener Evolution.

There was a slightly obscure idea in complex analysis called the Lowener differential equation. Essentially given any function on the real numbers I can associate a path in the complex plane that never crosses itself. It was clever, but never really took off as an idea.

Then a guy called Oded Schramm came along and solved the Lowener equation for a Brownian motion (A very random function) instead of a deterministic function.

The solutions of these are random paths in the complex plane that never cross themselves. It turns out they are also conformally invariant. (If I apply a differentiable complex function to the solution of the Lowener equation the probability distribution of the solution doesn't change.)

This area has seen a massive explosion of research in the last ten years. And there's an attempt to use these ideas to try and unite Quantum mechanics with gravity.

That's the only thing I can think of where there's a real union of complex analysis and probability theory. It's definitely not something I'm an expert on, and it's a seriously hard subject. (Two fields medals in the last ten years.) But it's probably worth your time having a look at what's going on in this area.

-

In the approach to uncertainty in which expectation is primitive (see, e.g., Bruno de Finetti, Frank Lad, Peter Whittle), a probability is defined as the expectation of the indicator function of a proposition. Random quantities and expectations can certainty be complex-valued, but probabilities are always real-valued because the indicator function only takes the real values 0 and 1.

-

Yes, quantum mechanics is an application of complex probability theory. If complex probabilities did not hold up in "pure math" they would continue to fall apart in QM and produce nonsensical results.

-
Quantum probability is a bit more than adding complex numbers to probability theory. In classical probability theory if two events $A$ and $B$ are independent then $\mathbb P(A\cap B) = \mathbb P(A)\times\mathbb P(B)$. In quantum probability multiplication is not commutitive. So $\mathbb P(A)\times\mathbb P(B)\neq\mathbb P(B)\times\mathbb P(A)$ so the probability of $A$ and $B$ depends on the order in which you multiply (or observe) them. It is true that complex numbers play a crucial role in QM. But I think it's misleading to say this is an application of complex probability theory. – Tim May 9 '13 at 22:57
Ummmm...that's kind of off the mark. The Copenhagen interpretation of QM (to which Einstein famously did not subscribe) states that the squared magnitude of the normalized wave function is a probability. – Ron Gordon May 9 '13 at 22:57
No sane physicist would ever talk about complex probabilities. The term used is probability amplitude to reflect the fact that the magnitude is all that's relevant to compute an actual probability ( – Sharkos May 10 '13 at 0:40
Perhaps it is indeed misleading to call this an application of complex probability theory since many calculations in QM are more interested maintaing the phase portion of a formula than it's normalized physical component. An example of this is indeed (as Sharkos points out) probability amplitude. – Phy51x May 10 '13 at 5:15
@Sharkos Regarding sane physicists, one famous physicist once observed (regarding the first years of QM), that this is just madness. And another replied, but it has a method. Now no sane physicist would claim that QM is madness. But this same sane physicist (esp. if a famous one) might still object to some other formulation which may be years ahead (all is in the method) – Nikos M. Jun 1 '14 at 2:57

One can indeed do that, for example have (exotic) probabilities which can be negative, or even greater than one etc..

For a simple introduction check this link

As a bonus, even quantum mechanics can be formulated (at least to some extend) as complex probabilities

Check also this post (which covers a different aspect), but which can be a possible application

UPDATE:

adding a comment i made here, since it answers criticism on complex probability, but also puts the discussion into the correct framework.

The very starting words on Kolmogorov's landmark work on axiomatization of probability theory states (not exact quote): "A probability is a number assigned to an event in an event space..". Now use some other number (and adjust the arithmetic accordingly) and you have a probability theory (maybe exotic but not less real)

In fact something very similar to exotic probabilities already exists in conventional (lets say) probability theory. It is called random variables. It seems people who downvoted this answer do not have a grasp of the extend of the random variables concept. What are random variables? Random Variables are ways to assign arbitrary numbers, arithmetic and measure to probabilistic events. What is exotic probability? (e.g complex probability), exactly the same. As some say same difference.

One can ask here, so if random variables already cover the functionality of exotic probability and is already a part of traditional probability theory, why should we be concerned with exotic places? Nice question, it is not necesary, in the same sense it is not necesary to use complex numbers instead just use 2 real numbers with specific rules of combination. Or use an array of numbers with special rules of combination instead of matrices, and so on and so forth. One can indeed do that, they are isomoprhic representations. It just happens some are natural representations and provide intuition, flexibility (and potentialy greater understanding) while others are not.

-


text:
# Illustration Voltage-Time Graph - charging capacitor

A capacitor with capacitance $$C$$ and a serially connected resistor $$R$$ is charged to voltage $$U_0$$. The time-dependent voltage $$U_{\text C}(t)$$ across the capacitor during the charging follows the exponential curve:$U_{\text C}(t) ~=~ U_0 \, \left(1 - e^{-\frac{t}{R\,C}}\right)$
As $$t$$ goes to infinity, the voltage $$U_{\text C}(t)$$ approaches the specified value of the source voltage $$U_0$$.


text:
You are currently browsing the tag archive for the ‘Kakeya conjecture’ tag.

This set of notes focuses on the restriction problem in Fourier analysis. Introduced by Elias Stein in the 1970s, the restriction problem is a key model problem for understanding more general oscillatory integral operators, and which has turned out to be connected to many questions in geometric measure theory, harmonic analysis, combinatorics, number theory, and PDE. Only partial results on the problem are known, but these partial results have already proven to be very useful or influential in many applications.
We work in a Euclidean space ${{\bf R}^d}$. Recall that ${L^p({\bf R}^d)}$ is the space of ${p^{th}}$-power integrable functions ${f: {\bf R}^d \rightarrow {\bf C}}$, quotiented out by almost everywhere equivalence, with the usual modifications when ${p=\infty}$. If ${f \in L^1({\bf R}^d)}$ then the Fourier transform ${\hat f: {\bf R}^d \rightarrow {\bf C}}$ will be defined in this course by the formula

$\displaystyle \hat f(\xi) := \int_{{\bf R}^d} f(x) e^{-2\pi i x \cdot \xi}\ dx. \ \ \ \ \ (1)$

From the dominated convergence theorem we see that ${\hat f}$ is a continuous function; from the Riemann-Lebesgue lemma we see that it goes to zero at infinity. Thus ${\hat f}$ lies in the space ${C_0({\bf R}^d)}$ of continuous functions that go to zero at infinity, which is a subspace of ${L^\infty({\bf R}^d)}$. Indeed, from the triangle inequality it is obvious that

$\displaystyle \|\hat f\|_{L^\infty({\bf R}^d)} \leq \|f\|_{L^1({\bf R}^d)}. \ \ \ \ \ (2)$

If ${f \in L^1({\bf R}^d) \cap L^2({\bf R}^d)}$, then Plancherel’s theorem tells us that we have the identity

$\displaystyle \|\hat f\|_{L^2({\bf R}^d)} = \|f\|_{L^2({\bf R}^d)}. \ \ \ \ \ (3)$

Because of this, there is a unique way to extend the Fourier transform ${f \mapsto \hat f}$ from ${L^1({\bf R}^d) \cap L^2({\bf R}^d)}$ to ${L^2({\bf R}^d)}$, in such a way that it becomes a unitary map from ${L^2({\bf R}^d)}$ to itself. By abuse of notation we continue to denote this extension of the Fourier transform by ${f \mapsto \hat f}$. Strictly speaking, this extension is no longer defined in a pointwise sense by the formula (1) (indeed, the integral on the RHS ceases to be absolutely integrable once ${f}$ leaves ${L^1({\bf R}^d)}$; we will return to the (surprisingly difficult) question of whether pointwise convergence continues to hold (at least in an almost everywhere sense) later in this course, when we discuss Carleson’s theorem. On the other hand, the formula (1) remains valid in the sense of distributions, and in practice most of the identities and inequalities one can show about the Fourier transform of “nice” functions (e.g., functions in ${L^1({\bf R}^d) \cap L^2({\bf R}^d)}$, or in the Schwartz class ${{\mathcal S}({\bf R}^d)}$, or test function class ${C^\infty_c({\bf R}^d)}$) can be extended to functions in “rough” function spaces such as ${L^2({\bf R}^d)}$ by standard limiting arguments.
By (2), (3), and the Riesz-Thorin interpolation theorem, we also obtain the Hausdorff-Young inequality

$\displaystyle \|\hat f\|_{L^{p'}({\bf R}^d)} \leq \|f\|_{L^p({\bf R}^d)} \ \ \ \ \ (4)$

for all ${1 \leq p \leq 2}$ and ${f \in L^1({\bf R}^d) \cap L^2({\bf R}^d)}$, where ${2 \leq p' \leq \infty}$ is the dual exponent to ${p}$, defined by the usual formula ${\frac{1}{p} + \frac{1}{p'} = 1}$. (One can improve this inequality by a constant factor, with the optimal constant worked out by Beckner, but the focus in these notes will not be on optimal constants.) As a consequence, the Fourier transform can also be uniquely extended as a continuous linear map from ${L^p({\bf R}^d) \rightarrow L^{p'}({\bf R}^d)}$. (The situation with ${p>2}$ is much worse; see below the fold.)
The restriction problem asks, for a given exponent ${1 \leq p \leq 2}$ and a subset ${S}$ of ${{\bf R}^d}$, whether it is possible to meaningfully restrict the Fourier transform ${\hat f}$ of a function ${f \in L^p({\bf R}^d)}$ to the set ${S}$. If the set ${S}$ has positive Lebesgue measure, then the answer is yes, since ${\hat f}$ lies in ${L^{p'}({\bf R}^d)}$ and therefore has a meaningful restriction to ${S}$ even though functions in ${L^{p'}}$ are only defined up to sets of measure zero. But what if ${S}$ has measure zero? If ${p=1}$, then ${\hat f \in C_0({\bf R}^d)}$ is continuous and therefore can be meaningfully restricted to any set ${S}$. At the other extreme, if ${p=2}$ and ${f}$ is an arbitrary function in ${L^2({\bf R}^d)}$, then by Plancherel’s theorem, ${\hat f}$ is also an arbitrary function in ${L^2({\bf R}^d)}$, and thus has no well-defined restriction to any set ${S}$ of measure zero.
It was observed by Stein (as reported in the Ph.D. thesis of Charlie Fefferman) that for certain measure zero subsets ${S}$ of ${{\bf R}^d}$, such as the sphere ${S^{d-1} := \{ \xi \in {\bf R}^d: |\xi| = 1\}}$, one can obtain meaningful restrictions of the Fourier transforms of functions ${f \in L^p({\bf R}^d)}$ for certain ${p}$ between ${1}$ and ${2}$, thus demonstrating that the Fourier transform of such functions retains more structure than a typical element of ${L^{p'}({\bf R}^d)}$:

Theorem 1 (Preliminary ${L^2}$ restriction theorem) If ${d \geq 2}$ and ${1 \leq p < \frac{4d}{3d+1}}$, then one has the estimate

$\displaystyle \| \hat f \|_{L^2(S^{d-1}, d\sigma)} \lesssim_{d,p} \|f\|_{L^p({\bf R}^d)}$

for all Schwartz functions ${f \in {\mathcal S}({\bf R}^d)}$, where ${d\sigma}$ denotes surface measure on the sphere ${S^{d-1}}$. In particular, the restriction ${\hat f|_S}$ can be meaningfully defined by continuous linear extension to an element of ${L^2(S^{d-1},d\sigma)}$.

Proof: Fix ${d,p,f}$. We expand out

$\displaystyle \| \hat f \|_{L^2(S^{d-1}, d\sigma)}^2 = \int_{S^{d-1}} |\hat f(\xi)|^2\ d\sigma(\xi).$

From (1) and Fubini’s theorem, the right-hand side may be expanded as

$\displaystyle \int_{{\bf R}^d} \int_{{\bf R}^d} f(x) \overline{f}(y) (d\sigma)^\vee(y-x)\ dx dy$

where the inverse Fourier transform ${(d\sigma)^\vee}$ of the measure ${d\sigma}$ is defined by the formula

$\displaystyle (d\sigma)^\vee(x) := \int_{S^{d-1}} e^{2\pi i x \cdot \xi}\ d\sigma(\xi).$

In other words, we have the identity

$\displaystyle \| \hat f \|_{L^2(S^{d-1}, d\sigma)}^2 = \langle f, f * (d\sigma)^\vee \rangle_{L^2({\bf R}^d)}, \ \ \ \ \ (5)$

using the Hermitian inner product ${\langle f, g\rangle_{L^2({\bf R}^d)} := \int_{{\bf R}^d} \overline{f(x)} g(x)\ dx}$. Since the sphere ${S^{d-1}}$ have bounded measure, we have from the triangle inequality that

$\displaystyle (d\sigma)^\vee(x) \lesssim_d 1. \ \ \ \ \ (6)$

Also, from the method of stationary phase (as covered in the previous class 247A), or Bessel function asymptotics, we have the decay

$\displaystyle (d\sigma)^\vee(x) \lesssim_d |x|^{-(d-1)/2} \ \ \ \ \ (7)$

for any ${x \in {\bf R}^d}$ (note that the bound already follows from (6) unless ${|x| \geq 1}$). We remark that the exponent ${-\frac{d-1}{2}}$ here can be seen geometrically from the following considerations. For ${|x|>1}$, the phase ${e^{2\pi i x \cdot \xi}}$ on the sphere is stationary at the two antipodal points ${x/|x|, -x/|x|}$ of the sphere, and constant on the tangent hyperplanes to the sphere at these points. The wavelength of this phase is proportional to ${1/|x|}$, so the phase would be approximately stationary on a cap formed by intersecting the sphere with a ${\sim 1/|x|}$ neighbourhood of the tangent hyperplane to one of the stationary points. As the sphere is tangent to second order at these points, this cap will have diameter ${\sim 1/|x|^{1/2}}$ in the directions of the ${d-1}$-dimensional tangent space, so the cap will have surface measure ${\sim |x|^{-(d-1)/2}}$, which leads to the prediction (7). We combine (6), (7) into the unified estimate

$\displaystyle (d\sigma)^\vee(x) \lesssim_d \langle x\rangle^{-(d-1)/2}, \ \ \ \ \ (8)$

where the “Japanese bracket” ${\langle x\rangle}$ is defined as ${\langle x \rangle := (1+|x|^2)^{1/2}}$. Since ${\langle x \rangle^{-\alpha}}$ lies in ${L^p({\bf R}^d)}$ precisely when ${p > \frac{d}{\alpha}}$, we conclude that

$\displaystyle (d\sigma)^\vee \in L^q({\bf R}^d) \hbox{ iff } q > \frac{d}{(d-1)/2}.$

Applying Young’s convolution inequality, we conclude (after some arithmetic) that

$\displaystyle \| f * (d\sigma)^\vee \|_{L^{p'}({\bf R}^d)} \lesssim_{p,d} \|f\|_{L^p({\bf R}^d)}$

whenever ${1 \leq p < \frac{4d}{3d+1}}$, and the claim now follows from (5) and Hölder’s inequality. $\Box$

Remark 2 By using the Hardy-Littlewood-Sobolev inequality in place of Young’s convolution inequality, one can also establish this result for ${p = \frac{4d}{3d+1}}$.

Motivated by this result, given any Radon measure ${\mu}$ on ${{\bf R}^d}$ and any exponents ${1 \leq p,q \leq \infty}$, we use ${R_\mu(p \rightarrow q)}$ to denote the claim that the restriction estimate

$\displaystyle \| \hat f \|_{L^q({\bf R}^d, \mu)} \lesssim_{d,p,q,\mu} \|f\|_{L^p({\bf R}^d)} \ \ \ \ \ (9)$

for all Schwartz functions ${f}$; if ${S}$ is a ${k}$-dimensional submanifold of ${{\bf R}^d}$ (possibly with boundary), we write ${R_S(p \rightarrow q)}$ for ${R_\mu(p \rightarrow q)}$ where ${\mu}$ is the ${k}$-dimensional surface measure on ${S}$. Thus, for instance, we trivially always have ${R_S(1 \rightarrow \infty)}$, while Theorem 1 asserts that ${R_{S^{d-1}}(p \rightarrow 2)}$ holds whenever ${1 \leq p < \frac{4d}{3d+1}}$. We will not give a comprehensive survey of restriction theory in these notes, but instead focus on some model results that showcase some of the basic techniques in the field. (I have a more detailed survey on this topic from 2003, but it is somewhat out of date.)
Read the rest of this entry »

I have just uploaded to the arXiv my paper “Sharp bounds for multilinear curved Kakeya, restriction and oscillatory integral estimates away from the endpoint“, submitted to Mathematika. In this paper I return (after more than a decade’s absence) to one of my first research interests, namely the Kakeya and restriction family of conjectures. The starting point is the following “multilinear Kakeya estimate” first established in the non-endpoint case by Bennett, Carbery, and myself, and then in the endpoint case by Guth (with further proofs and extensions by Bourgain-Guth and Carbery-Valdimarsson:

Theorem 1 (Multilinear Kakeya estimate) Let ${\delta > 0}$ be a radius. For each ${j = 1,\dots,d}$, let ${\mathbb{T}_j}$ denote a finite family of infinite tubes ${T_j}$ in ${{\bf R}^d}$ of radius ${\delta}$. Assume the following axiom:

• (i) (Transversality) whenever ${T_j \in \mathbb{T}_j}$ is oriented in the direction of a unit vector ${n_j}$ for ${j =1,\dots,d}$, we have

$\displaystyle \left|\bigwedge_{j=1}^d n_j\right| \geq A^{-1}$

for some ${A>0}$, where we use the usual Euclidean norm on the wedge product ${\bigwedge^d {\bf R}^d}$.

Then, for any ${p \geq \frac{1}{d-1}}$, one has

$\displaystyle \left\| \prod_{j=1}^d \sum_{T_j \in \mathbb{T}_j} 1_{T_j} \right\|_{L^p({\bf R}^d)} \lesssim_{A,p} \delta^{\frac{d}{p}} \prod_{j \in [d]} \# \mathbb{T}_j. \ \ \ \ \ (1)$

where ${L^p({\bf R}^d)}$ are the usual Lebesgue norms with respect to Lebesgue measure, ${1_{T_j}}$ denotes the indicator function of ${T_j}$, and ${\# \mathbb{T}_j}$ denotes the cardinality of ${\mathbb{T}_j}$.

The original proof of this proceeded using a heat flow monotonicity method, which in my previous post I reinterpreted using a “virtual integration” concept on a fractional Cartesian product space. It turns out that this machinery is somewhat flexible, and can be used to establish some other estimates of this type. The first result of this paper is to extend the above theorem to the curved setting, in which one localises to a ball of radius ${O(1)}$ (and sets ${\delta}$ to be small), but allows the tubes ${T_j}$ to be curved in a ${C^2}$ fashion. If one runs the heat flow monotonicity argument, one now picks up some additional error terms arising from the curvature, but as the spatial scale approaches zero, the tubes become increasingly linear, and as such the error terms end up being an integrable multiple of the main term, at which point one can conclude by Gronwall’s inequality (actually for technical reasons we use a bootstrap argument instead of Gronwall). A key point in this approach is that one obtains optimal bounds (not losing factors of ${\delta^{-\varepsilon}}$ or ${\log^{O(1)} \frac{1}{\delta}}$), so long as one stays away from the endpoint case ${p=\frac{1}{d-1}}$ (which does not seem to be easily treatable by the heat flow methods). Previously, the paper of Bennett, Carbery, and myself was able to use an induction on scale argument to obtain a curved multilinear Kakeya estimate losing a factor of ${\log^{O(1)} \frac{1}{\delta}}$ (after optimising the argument); later arguments of Bourgain-Guth and Carbery-Valdimarsson, based on algebraic topology methods, could also obtain a curved multilinear Kakeya estimate without such losses, but only in the algebraic case when the tubes were neighbourhoods of algebraic curves of bounded degree.

Perhaps more interestingly, we are also able to extend the heat flow monotonicity method to apply directly to the multilinear restriction problem, giving the following global multilinear restriction estimate:

Theorem 2 (Multilinear restriction theorem) Let ${\frac{1}{d-1} < p \leq \infty}$ be an exponent, and let ${A \geq 2}$ be a parameter. Let ${M}$ be a sufficiently large natural number, depending only on ${d}$. For ${j \in [d]}$, let ${U_j}$ be an open subset of ${B^{d-1}(0,A)}$, and let ${h_j: U_j \rightarrow {\bf R}}$ be a smooth function obeying the following axioms:

• (i) (Regularity) For each ${j \in [d]}$ and ${\xi \in U_j}$, one has

$\displaystyle |\nabla_\xi^{\otimes m} \otimes h_j(\xi)| \leq A \ \ \ \ \ (2)$

for all ${1 \leq m \leq M}$.

• (ii) (Transversality) One has

$\displaystyle \left| \bigwedge_{j \in [d]} (-\nabla_\xi h_j(\xi_j),1) \right| \geq A^{-1}$

whenever ${\xi_j \in U_j}$ for ${j \in [d]}$.

Let ${U_{j,1/A} \subset U_j}$ be the sets

$\displaystyle U_{j,1/A} := \{ \xi \in U_j: B^{d-1}(\xi,1/A) \subset U_j \}. \ \ \ \ \ (3)$

Then one has

$\displaystyle \left\| \prod_{j \in [d]} {\mathcal E}_j f_j \right\|_{L^{2p}({\bf R}^d)} \leq A^{O(1)} \left(d-1-\frac{1}{p}\right)^{-O(1)} \prod_{j \in [d]} \|f_j \|_{L^2(U_{j,1/A})}$

for any ${f_j \in L^2(U_{j,1/A} \rightarrow {\bf C})}$, ${j \in [d]}$, extended by zero outside of ${U_{j,1/A}}$, and ${{\mathcal E}_j}$ denotes the extension operator

$\displaystyle {\mathcal E}_j f_j( x', x_d ) := \int_{U_j} e^{2\pi i (x' \xi^T + x_d h_j(\xi))} f_j(\xi)\ d\xi.$

Local versions of such estimate, in which ${L^{2p}({\bf R}^d)}$ is replaced with ${L^{2p}(B^d(0,R))}$ for some ${R \geq 2}$, and one accepts a loss of the form ${\log^{O(1)} R}$, were already established by Bennett, Carbery, and myself using an induction on scale argument. In a later paper of Bourgain-Guth these losses were removed by “epsilon removal lemmas” to recover Theorme 2, but only in the case when all the hypersurfaces involved had curvatures bounded away from zero.

There are two main new ingredients in the proof of Theorem 2. The first is to replace the usual induction on scales scheme to establish multilinear restriction by a “ball inflation” induction on scales scheme that more closely resembles the proof of decoupling theorems. In particular, we actually prove the more general family of estimates

$\displaystyle \left\| \prod_{j \in [d]} E_{r}[{\mathcal E}_j f_j] \right\|_{L^{p}({\bf R}^d)} \leq A^{O(1)} \left(d-1 - \frac{1}{p}\right)^{O(1)} r^{\frac{d}{p}} \prod_{j \in [d]} \| f_j \|_{L^2(U_{j,1/A})}^2$

where ${E_r}$ denotes the local energies

$\displaystyle E_{r}[f](x',x_d) := \int_{B^{d-1}(x',r)} |f(y',x_d)|^2\ dy'$

(actually for technical reasons it is more convenient to use a smoother weight than the strict cutoff to the disk ${B^{d-1}(x',r)}$). With logarithmic losses, it is not difficult to establish this estimate by an upward induction on ${r}$. To avoid such losses we use the heat flow monotonicity method. Here we run into the issue that the extension operators ${{\mathcal E}_j f_j}$ are complex-valued rather than non-negative, and thus would not be expected to obey many good montonicity properties. However, the local energies ${E_r[{\mathcal E}_j f_j]}$ can be expressed in terms of the magnitude squared of what is essentially the Gabor transform of ${{\mathcal E}_j f_j}$, and these are non-negative; furthermore, the dispersion relation associated to the extension operators ${{\mathcal E}_j f_j}$ implies that these Gabor transforms propagate along tubes, so that the situation becomes quite similar (up to several additional lower order error terms) to that in the multilinear Kakeya problem. (This can be viewed as a continuous version of the usual wave packet decomposition method used to relate restriction and Kakeya problems, which when combined with the heat flow monotonicity method allows for one to use a continuous version of induction on scales methods that do not concede any logarithmic factors.)

Finally, one can combine the curved multilinear Kakeya result with the multilinear restriction result to obtain estimates for multilinear oscillatory integrals away from the endpoint. Again, this sort of implication was already established in the previous paper of Bennett, Carbery, and myself, but the arguments there had some epsilon losses in the exponents; here we were able to run the argument more carefully and avoid these losses.

This is a blog version of a talk I recently gave at the IPAM workshop on “The Kakeya Problem, Restriction Problem, and Sum-product Theory”.

Note: the discussion here will be highly non-rigorous in nature, being extremely loose in particular with asymptotic notation and with the notion of dimension. Caveat emptor.

One of the most infamous unsolved problems at the intersection of geometric measure theory, incidence combinatorics, and real-variable harmonic analysis is the Kakeya set conjecture. We will focus on the following three-dimensional case of the conjecture, stated informally as follows:

Conjecture 1 (Kakeya conjecture) Let ${E}$ be a subset of ${{\bf R}^3}$ that contains a unit line segment in every direction. Then ${\hbox{dim}(E) = 3}$.

This conjecture is not precisely formulated here, because we have not specified exactly what type of set ${E}$ is (e.g. measurable, Borel, compact, etc.) and what notion of dimension we are using. We will deliberately ignore these technical details in this post. It is slightly more convenient for us here to work with lines instead of unit line segments, so we work with the following slight variant of the conjecture (which is essentially equivalent):

Conjecture 2 (Kakeya conjecture, again) Let ${{\cal L}}$ be a family of lines in ${{\bf R}^3}$ that meet ${B(0,1)}$ and contain a line in each direction. Let ${E}$ be the union of the restriction ${\ell \cap B(0,2)}$ to ${B(0,2)}$ of every line ${\ell}$ in ${{\cal L}}$. Then ${\hbox{dim}(E) = 3}$.

As the space of all directions in ${{\bf R}^3}$ is two-dimensional, we thus see that ${{\cal L}}$ is an (at least) two-dimensional subset of the four-dimensional space of lines in ${{\bf R}^3}$ (actually, it lies in a compact subset of this space, since we have constrained the lines to meet ${B(0,1)}$). One could then ask if this is the only property of ${{\cal L}}$ that is needed to establish the Kakeya conjecture, that is to say if any subset of ${B(0,2)}$ which contains a two-dimensional family of lines (restricted to ${B(0,2)}$, and meeting ${B(0,1)}$) is necessarily three-dimensional. Here we have an easy counterexample, namely a plane in ${B(0,2)}$ (passing through the origin), which contains a two-dimensional collection of lines. However, we can exclude this case by adding an additional axiom, leading to what one might call a “strong” Kakeya conjecture:

Conjecture 3 (Strong Kakeya conjecture) Let ${{\cal L}}$ be a two-dimensional family of lines in ${{\bf R}^3}$ that meet ${B(0,1)}$, and assume the Wolff axiom that no (affine) plane contains more than a one-dimensional family of lines in ${{\cal L}}$. Let ${E}$ be the union of the restriction ${\ell \cap B(0,2)}$ of every line ${\ell}$ in ${{\cal L}}$. Then ${\hbox{dim}(E) = 3}$.

Actually, to make things work out we need a more quantitative version of the Wolff axiom in which we constrain the metric entropy (and not just dimension) of lines that lie close to a plane, rather than exactly on the plane. However, for the informal discussion here we will ignore these technical details. Families of lines that lie in different directions will obey the Wolff axiom, but the converse is not true in general.

In 1995, Wolff established the important lower bound ${\hbox{dim}(E) \geq 5/2}$ (for various notions of dimension, e.g. Hausdorff dimension) for sets ${E}$ in Conjecture 3 (and hence also for the other forms of the Kakeya problem). However, there is a key obstruction to going beyond the ${5/2}$ barrier, coming from the possible existence of half-dimensional (approximate) subfields of the reals ${{\bf R}}$. To explain this problem, it easiest to first discuss the complex version of the strong Kakeya conjecture, in which all relevant (real) dimensions are doubled:

Conjecture 4 (Strong Kakeya conjecture over ${{\bf C}}$) Let ${{\cal L}}$ be a four (real) dimensional family of complex lines in ${{\bf C}^3}$ that meet the unit ball ${B(0,1)}$ in ${{\bf C}^3}$, and assume the Wolff axiom that no four (real) dimensional (affine) subspace contains more than a two (real) dimensional family of complex lines in ${{\cal L}}$. Let ${E}$ be the union of the restriction ${\ell \cap B(0,2)}$ of every complex line ${\ell}$ in ${{\cal L}}$. Then ${E}$ has real dimension ${6}$.

The argument of Wolff can be adapted to the complex case to show that all sets ${E}$ occuring in Conjecture 4 have real dimension at least ${5}$. Unfortunately, this is sharp, due to the following fundamental counterexample:

Proposition 5 (Heisenberg group counterexample) Let ${H \subset {\bf C}^3}$ be the Heisenberg group

$\displaystyle H = \{ (z_1,z_2,z_3) \in {\bf C}^3: \hbox{Im}(z_1) = \hbox{Im}(z_2 \overline{z_3}) \}$

and let ${{\cal L}}$ be the family of complex lines

$\displaystyle \ell_{s,t,\alpha} := \{ (\overline{\alpha} z + t, z, sz + \alpha): z \in {\bf C} \}$

with ${s,t \in {\bf R}}$ and ${\alpha \in {\bf C}}$. Then ${H}$ is a five (real) dimensional subset of ${{\bf C}^3}$ that contains every line in the four (real) dimensional set ${{\cal L}}$; however each four real dimensional (affine) subspace contains at most a two (real) dimensional set of lines in ${{\cal L}}$. In particular, the strong Kakeya conjecture over the complex numbers is false.

This proposition is proven by a routine computation, which we omit here. The group structure on ${H}$ is given by the group law

$\displaystyle (z_1,z_2,z_3) \cdot (w_1,w_2,w_3) = (z_1 + w_1 + z_2 \overline{w_3} - z_3 \overline{w_2}, z_2 +w_2, z_3+w_3),$

giving ${E}$ the structure of a ${2}$-step simply-connected nilpotent Lie group, isomorphic to the usual Heisenberg group over ${{\bf R}^2}$. Note that while the Heisenberg group is a counterexample to the complex strong Kakeya conjecture, it is not a counterexample to the complex form of the original Kakeya conjecture, because the complex lines ${{\cal L}}$ in the Heisenberg counterexample do not point in distinct directions, but instead only point in a three (real) dimensional subset of the four (real) dimensional space of available directions for complex lines. For instance, one has the one real-dimensional family of parallel lines

$\displaystyle \ell_{0,t,0} = \{ (t, z, 0): z \in {\bf C}\}$

with ${t \in {\bf R}}$; multiplying this family of lines on the right by a group element in ${H}$ gives other families of parallel lines, which in fact sweep out all of ${{\cal L}}$.

The Heisenberg counterexample ultimately arises from the “half-dimensional” (and hence degree two) subfield ${{\bf R}}$ of ${{\bf C}}$, which induces an involution ${z \mapsto \overline{z}}$ which can then be used to define the Heisenberg group ${H}$ through the formula

$\displaystyle H = \{ (z_1,z_2,z_3) \in {\bf C}^3: z_1 - \overline{z_1} = z_2 \overline{z_3} - z_3 \overline{z_2} \}.$

Analogous Heisenberg counterexamples can also be constructed if one works over finite fields ${{\bf F}_{q^2}}$ that contain a “half-dimensional” subfield ${{\bf F}_q}$; we leave the details to the interested reader. Morally speaking, if ${{\bf R}}$ in turn contained a subfield of dimension ${1/2}$ (or even a subring or “approximate subring”), then one ought to be able to use this field to generate a counterexample to the strong Kakeya conjecture over the reals. Fortunately, such subfields do not exist; this was a conjecture of Erdos and Volkmann that was proven by Edgar and Miller, and more quantitatively by Bourgain (answering a question of Nets Katz and myself). However, this fact is not entirely trivial to prove, being a key example of the sum-product phenomenon.

We thus see that to go beyond the ${5/2}$ dimension bound of Wolff for the 3D Kakeya problem over the reals, one must do at least one of two things:

• (a) Exploit the distinct directions of the lines in ${{\mathcal L}}$ in a way that goes beyond the Wolff axiom; or
• (b) Exploit the fact that ${{\bf R}}$ does not contain half-dimensional subfields (or more generally, intermediate-dimensional approximate subrings).

(The situation is more complicated in higher dimensions, as there are more obstructions than the Heisenberg group; for instance, in four dimensions quadric surfaces are an important obstruction, as discussed in this paper of mine.)

Various partial or complete results on the Kakeya problem over various fields have been obtained through route (a) or route (b). For instance, in 2000, Nets Katz, Izabella Laba and myself used route (a) to improve Wolff’s lower bound of ${5/2}$ for Kakeya sets very slightly to ${5/2+10^{-10}}$ (for a weak notion of dimension, namely upper Minkowski dimension). In 2004, Bourgain, Katz, and myself established a sum-product estimate which (among other things) ruled out approximate intermediate-dimensional subrings of ${{\bf F}_p}$, and then pursued route (b) to obtain a corresponding improvement ${5/2+\epsilon}$ to the Kakeya conjecture over finite fields of prime order. The analogous (discretised) sum-product estimate over the reals was established by Bourgain in 2003, which in principle would allow one to extend the result of Katz, Laba and myself to the strong Kakeya setting, but this has not been carried out in the literature. Finally, in 2009, Dvir used route (a) and introduced the polynomial method (as discussed previously here) to completely settle the Kakeya conjecture in finite fields.

Below the fold, I present a heuristic argument of Nets Katz and myself, which in principle would use route (b) to establish the full (strong) Kakeya conjecture. In broad terms, the strategy is as follows:

1. Assume that the (strong) Kakeya conjecture fails, so that there are sets ${E}$ of the form in Conjecture 3 of dimension ${3-\sigma}$ for some ${\sigma>0}$. Assume that ${E}$ is “optimal”, in the sense that ${\sigma}$ is as large as possible.
2. Use the optimality of ${E}$ (and suitable non-isotropic rescalings) to establish strong forms of standard structural properties expected of such sets ${E}$, namely “stickiness”, “planiness”, “local graininess” and “global graininess” (we will roughly describe these properties below). Heuristically, these properties are constraining ${E}$ to “behave like” a putative Heisenberg group counterexample.
3. By playing all these structural properties off of each other, show that ${E}$ can be parameterised locally by a one-dimensional set which generates a counterexample to Bourgain’s sum-product theorem. This contradiction establishes the Kakeya conjecture.

Nets and I have had an informal version of argument for many years, but were never able to make a satisfactory theorem (or even a partial Kakeya result) out of it, because we could not rigorously establish anywhere near enough of the necessary structural properties (stickiness, planiness, etc.) on the optimal set ${E}$ for a large number of reasons (one of which being that we did not have a good notion of dimension that did everything that we wished to demand of it). However, there is beginning to be movement in these directions (e.g. in this recent result of Guth using the polynomial method obtaining a weak version of local graininess on certain Kakeya sets). In view of this (and given that neither Nets or I have been actively working in this direction for some time now, due to many other projects), we’ve decided to distribute these ideas more widely than before, and in particular on this blog.

In this post I would like to make some technical notes on a standard reduction used in the (Euclidean, maximal) Kakeya problem, known as the two ends reduction. This reduction (which takes advantage of the approximate scale-invariance of the Kakeya problem) was introduced by Wolff, and has since been used many times, both for the Kakeya problem and in other similar problems (e.g. by Jim Wright and myself to study curved Radon-like transforms). I was asked about it recently, so I thought I would describe the trick here. As an application I give a proof of the ${d=\frac{n+1}{2}}$ case of the Kakeya maximal conjecture.

Below the fold is a version of my talk “Recent progress on the Kakeya conjecture” that I gave at the Fefferman conference.

Jordan Ellenberg, Richard Oberlin, and I have just uploaded to the arXiv the paper “The Kakeya set and maximal conjectures for algebraic varieties over finite fields“, submitted to Mathematika.  This paper builds upon some work of Dvir and later authors on the Kakeya problem in finite fields, which I have discussed in this earlier blog post.  Dvir established the following:

Kakeya set conjecture for finite fields. Let F be a finite field, and let E be a subset of $F^n$ that contains a line in every direction.  Then E has cardinality at least $c_n |F|^n$ for some $c_n > 0$.

The initial argument of Dvir gave $c_n = 1/n!$.  This was improved to $c_n = c^n$ for some explicit $0 < c < 1$ by Saraf and Sudan, and recently to $c_n =1/2^n$ by Dvir, Kopparty, Saraf, and Sudan, which is within a factor 2 of the optimal result.

In our work we investigate a somewhat different set of improvements to Dvir’s result.  The first concerns the Kakeya maximal function $f^*: {\Bbb P}^{n-1}(F) \to {\Bbb R}$ of a function $f: F^n \to {\Bbb R}$, defined for all directions $\xi \in {\Bbb P}^{n-1}(F)$ in the projective hyperplane at infinity by the formula

$f^*(\xi) = \sup_{\ell // \xi} \sum_{x \in \ell} |f(x)|$

where the supremum ranges over all lines $\ell$ in $F^n$ oriented in the direction $\xi$.  Our first result is the endpoint $L^p$ estimate for this operator, namely

Kakeya maximal function conjecture in finite fields. We have $\| f^* \|_{\ell^n({\Bbb P}^{n-1}(F))} \leq C_n |F|^{(n-1)/n} \|f\|_{\ell^n(F^n)}$ for some constant $C_n > 0$.

This result implies Dvir’s result, since if f is the indicator function of the set E in Dvir’s result, then $f^*(\xi) = |F|$ for every $\xi \in {\Bbb P}^{n-1}(F)$.  However, it also gives information on more general sets E which do not necessarily contain a line in every direction, but instead contain a certain fraction of a line in a subset of directions.  The exponents here are best possible in the sense that all other $\ell^p \to \ell^q$ mapping properties of the operator can be deduced (with bounds that are optimal up to constants) by interpolating the above estimate with more trivial estimates.  This result is the finite field analogue of a long-standing (and still open) conjecture for the Kakeya maximal function in Euclidean spaces; we rely on the polynomial method of Dvir, which thus far has not extended to the Euclidean setting (but note the very interesting variant of this method by Guth that has established the endpoint multilinear Kakeya maximal function estimate in this setting, see this blog post for further discussion).

It turns out that a direct application of the polynomial method is not sufficient to recover the full strength of the maximal function estimate; but by combining the polynomial method with the Nikishin-Maurey-Pisier-Stein “method of random rotations” (as interpreted nowadays by Stein and later by Bourgain, and originally inspired by the factorisation theorems of Nikishin, Maurey, and Pisier), one can already recover a “restricted weak type” version of the above estimate.  If one then enhances the polynomial method with the “method of multiplicities” (as introduced by Saraf and Sudan) we can then recover the full “strong type” estimate; a few more details below the fold.

It turns out that one can generalise the above results to more general affine or projective algebraic varieties over finite fields.  In particular, we showed

Kakeya maximal function conjecture in algebraic varieties. Suppose that $W \subset {\Bbb P}^N$ is an (n-1)-dimensional algebraic variety.  Let $d \geq 1$ be an integer. Then we have

$\| \sup_{\gamma \ni x; \gamma \not \subset W} \sum_{y \in \gamma} f(y) \|_{\ell^n_x(W(F))} \leq C_{n,d,N,W} |F|^{(n-1)/n} \|f\|_{\ell^n({\Bbb P}^N(F))}$

for some constant $C_{n,d,N,W} > 0$, where the supremum is over all irreducible algebraic curves $\gamma$ of degree at most d that pass through x but do not lie in W, and W(F) denotes the F-points of W.

The ordinary Kakeya maximal function conjecture corresponds to the case when N=n, W is the hyperplane at infinity, and the degree d is equal to 1.  One corollary of this estimate is a Dvir-type result: a subset of ${\Bbb P}^N(F)$ which contains, for each x in W, an irreducible algebraic curve of degree d passing through x but not lying in W, has cardinality $\gg |F|^n$ if $|W| \gg |F|^{n-1}$.  (In particular this implies a lower bound for Nikodym sets worked out by Li.)  The dependence of the implied constant on W is only via the degree of W.

The techniques used in the flat case can easily handle curves $\gamma$ of higher degree (provided that we allow the implied constants to depend on d), but the method of random rotations does not seem to work directly on the algebraic variety W as there are usually no symmetries of this variety to exploit.  Fortunately, we can get around this by using a “random projection trick” to “flatten” W into a hyperplane (after first expressing W as the zero locus of some polynomials, and then composing with the graphing map for such polynomials), reducing the non-flat case to the flat case.

Below the fold, I wish to sketch two of the key ingredients in our arguments, the random rotations method and the random projections trick.  (We of course also use some algebraic geometry, but mostly low-tech stuff, on the level of Bezout’s theorem, though we do need one non-trivial result of Kleiman (from SGA6), that asserts that bounded degree varieties can be cut out by a bounded number of polynomials of bounded degree.)

[Update, March 14: See also Jordan’s own blog post on our paper.]

In 1917, Soichi Kakeya posed the following problem:

Kakeya needle problem. What is the least amount of area required to continuously rotate a unit line segment in the plane by a full rotation (i.e. by $360^\circ$)?

In 1928, Besicovitch showed that given any $\varepsilon > 0$, there exists a planar set of area at most $\varepsilon$ within which a unit needle can be continuously rotated; the proof relies on the construction of what is now known as a Besicovitch set – a set of measure zero in the plane which contains a unit line segment in every direction.  So the answer to the Kakeya needle problem is “zero”.

I was recently asked (by Claus Dollinger) whether one can take $\varepsilon = 0$; in other words,

Question. Does there exist a set of measure zero within which a unit line segment can be continuously rotated by a full rotation?

This question does not seem to be explicitly answered in the literature.  In the papers of von Alphen and of Cunningham, it is shown that it is possible to continuously rotate a unit line segment inside a set of arbitrarily small measure and of uniformly bounded diameter; this result is of course implied by a positive answer to the above question (since continuous functions on compact sets are bounded), but the converse is not true.

Below the fold, I give the answer to the problem… but perhaps readers may wish to make a guess as to what the answer is first before proceeding, to see how good their real analysis intuition is.  (To partially prevent spoilers for those reading this post via RSS, I will be whitening the text; you will have to highlight the text in order to see it.  Unfortunately, I do not know how to white out the LaTeX in such a way that it is visible upon highlighting, so RSS readers may wish to stop reading right now; but I suppose one can view the LaTeX as supplying hints to the problem, without giving away the full solution.)

[Update, March 13: a non-whitened version of this article can be found as part of this book.]

One of my favourite family of conjectures (and one that has preoccupied a significant fraction of my own research) is the family of Kakeya conjectures in geometric measure theory and harmonic analysis.  There are many (not quite equivalent) conjectures in this family.  The cleanest one to state is the set conjecture:

Kakeya set conjecture: Let $n \geq 1$, and let $E \subset {\Bbb R}^n$ contain a unit line segment in every direction (such sets are known as Kakeya sets or Besicovitch sets).  Then E has Hausdorff dimension and Minkowski dimension equal to n.

One reason why I find these conjectures fascinating is the sheer variety of mathematical fields that arise both in the partial results towards this conjecture, and in the applications of those results to other problems.  See for instance this survey of Wolff, my Notices article and this article of Łaba on the connections between this problem and other problems in Fourier analysis, PDE, and additive combinatorics; there have even been some connections to number theory and to cryptography.  At the other end of the pipeline, the mathematical tools that have gone into the proofs of various partial results have included:

[This list is not exhaustive.]

Very recently, I was pleasantly surprised to see yet another mathematical tool used to obtain new progress on the Kakeya conjecture, namely (a generalisation of) the famous Ham Sandwich theorem from algebraic topology.  This was recently used by Guth to establish a certain endpoint multilinear Kakeya estimate left open by the work of Bennett, Carbery, and myself.  With regards to the Kakeya set conjecture, Guth’s arguments assert, roughly speaking, that the only Kakeya sets that can fail to have full dimension are those which obey a certain “planiness” property, which informally means that the line segments that pass through a typical point in the set must be essentially coplanar. (This property first surfaced in my paper with Katz and Łaba.)  Guth’s arguments can be viewed as a partial analogue of Dvir’s arguments in the finite field setting (which I discussed in this blog post) to the Euclidean setting; in particular, both arguments rely crucially on the ability to create a polynomial of controlled degree that vanishes at or near a large number of points.  Unfortunately, while these arguments fully settle the Kakeya conjecture in the finite field setting, it appears that some new ideas are still needed to finish off the problem in the Euclidean setting.  Nevertheless this is an interesting new development in the long history of this conjecture, in particular demonstrating that the polynomial method can be successfully applied to continuous Euclidean problems (i.e. it is not confined to the finite field setting).

In this post I would like to sketch some of the key ideas in Guth’s paper, in particular the role of the Ham Sandwich theorem (or more precisely, a polynomial generalisation of this theorem first observed by Gromov).

One of my favourite unsolved problems in mathematics is the Kakeya conjecture in geometric measure theory. This conjecture is descended from the

Kakeya needle problem. (1917) What is the least area in the plane required to continuously rotate a needle of unit length and zero thickness around completely (i.e. by $360^\circ$)?

For instance, one can rotate a unit needle inside a unit disk, which has area $\pi/4$. By using a deltoid one requires only $\pi/8$ area.

In 1928, Besicovitch showed that that in fact one could rotate a unit needle using an arbitrarily small amount of positive area. This unintuitive fact was a corollary of two observations. The first, which is easy, is that one can translate a needle using arbitrarily small area, by sliding the needle along the direction it points in for a long distance (which costs zero area), turning it slightly (costing a small amount of area), sliding back, and then undoing the turn. The second fact, which is less obvious, can be phrased as follows. Define a Kakeya set in ${\Bbb R}^2$ to be any set which contains a unit line segment in each direction. (See this Java applet of mine, or the wikipedia page, for some pictures of such sets.)

Theorem. (Besicovitch, 1919) There exists Kakeya sets ${\Bbb R}^2$ of arbitrarily small area (or more precisely, Lebesgue measure).

In fact, one can construct such sets with zero Lebesgue measure. On the other hand, it was shown by Davies that even though these sets had zero area, they were still necessarily two-dimensional (in the sense of either Hausdorff dimension or Minkowski dimension). This led to an analogous conjecture in higher dimensions:

Kakeya conjecture. A Besicovitch set in ${\Bbb R}^n$ (i.e. a subset of ${\Bbb R}^n$ that contains a unit line segment in every direction) has Minkowski and Hausdorff dimension equal to n.

This conjecture remains open in dimensions three and higher (and gets more difficult as the dimension increases), although many partial results are known. For instance, when n=3, it is known that Besicovitch sets have Hausdorff dimension at least 5/2 and (upper) Minkowski dimension at least $5/2 + 10^{-10}$. See my Notices article for a general survey of this problem (and its connections with Fourier analysis, additive combinatorics, and PDE), my paper with Katz for a more technical survey, and Wolff’s survey for a systematic treatment of the field (up to about 1998 or so).

In 1999, Wolff proposed a simpler finite field analogue of the Kakeya conjecture as a model problem that avoided all the technical issues involving Minkowski and Hausdorff dimension. If $F^n$ is a vector space over a finite field F, define a Kakeya set to be a subset of $F^n$ which contains a line in every direction.

Finite field Kakeya conjecture. Let $E \subset F^n$ be a Kakeya set. Then E has cardinality at least $c_n |F|^n$, where $c_n > 0$ depends only on n.

This conjecture has had a significant influence in the subject, in particular inspiring work on the sum-product phenomenon in finite fields, which has since proven to have many applications in number theory and computer science. Modulo minor technicalities, the progress on the finite field Kakeya conjecture was, until very recently, essentially the same as that of the original “Euclidean” Kakeya conjecture.

Last week, the finite field Kakeya conjecture was proven using a beautifully simple argument by Zeev Dvir, using the polynomial method in algebraic extremal combinatorics. The proof is so short that I can present it in full here.


text:
# Find and correct the errors in the statement: x + 2x + 3x = 5x

81 views
Find and correct the errors in the statement:

x + 2x + 3x = 5x

by (24.8k points)
selected

L.H.S = x + 2x + 3x =1x + 2x + 3x = x(1 + 2 + 3)

= 6x ≠ R.H.S.

The correct statement is x + 2x + 3x = 6x


text:
×

# Constructing a triangle given three circles

Given three co-planar, concentric circles of radii,$$r_{1}$$ $$r_{2}$$ $$r_{3}$$ ,how can one construct an equilateral triangle such that each vertex of the triangle lies on a different circle.
Assume that the radii are given such that a solution is possible