order theory – Verification of a maximal antichain

In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the antichain which is not properly contained in another antichain. Let’s take the power set of ${1,2,ldots, n}$ as our partially-ordered set, here the order is given by inclusion. Then my question is, for any given antichain of this partially-orded set, is there any polynomial-time algorithm (with respect to $n$) to verify that this antichain is indeed “maximal”? In other words, verifying that any subset of ${1,2,ldots, n}$ is either contained in, or contains some set from the antichain. Here such algorithm should have polynomial run-time for ANY antichain.

email – How should I handle the problem of people entering others’ e-mail addresses without annoying them with “verification” e-mails?

I have forms on my in-development website which require the person to enter an e-mail address.

I don’t want to have to send them a “verification” e-mail with a URL containing a code, or instructions such as “please reply to this e-mail to verify that you sent it”. This is extremely likely to cause problems such as them not receiving it, or not seeing it, or forgetting about it, or don’t want to click on URLs for whatever reason. I know that it’s “best practice” according to numerous online guides for e-mail, but in reality, it’s a major chore for everyone involved.

And having a text such as:

If you wish, you can click this link to verify that you sent this: blablabla

feels pointless since most will not bother unless they have to.

If somebody enters a nasty message into the form and states their enemy’s e-mail address, my system will therefore assume that the person owning that e-mail address submitted the form, and perhaps I will add him to my “blackhole list” without considering that it may not be them. And then, when they later actually want to use the service, they can’t, because I added them to my list of e-mail addresses to silently ignore, because some entirely different person “framed” them.

Maybe this doesn’t happen often in practice, but I’ve had it happen to me personally, so I know that it does happen, at least sometimes. I’ve received angry e-mails from people replying to me after somebody wrote something mean and used my e-mail address.

algebraic topology – Proof Verification: Only contractible discrete space is the one point space

I am trying to prove that only contractible discrete space is the one point space. The proof of it can be seen here(https://math.stackexchange.com/questions/2218782/show-that-discrete-space-of-x-is-contractible-if-have-one-point) and here(https://math.stackexchange.com/questions/1720201/proving-that-a-three-point-discrete-space-is-not-contractible)

I believe I have a proof, but I do not use connectedness of the unit interval, so I’m asking for verification of my proof.

My proof

Suppose discrete space X was contractible. Any contractible space is path-connected. Indeed, take a homotopy $H colon X times (0,1) to X$ from identity on $X$ to $cost$ on $x_1$. Then for any $x_2 in X$, $H(x_2, -) colon (0,1) to X$ gives a path from $x_1$ to $x_2$ as $H$ being continuous implies $H$ is continuous in each variable.

Now I claim that any discrete space with more than 2 points is not connected. To show this, note that if there is continuous and non-constant map $X to {0,1}$, then $X$ is not connected. As $X$ has more than 2 points, we can find a non-constant set map $X to {0,1}$. And as $X$ is discrete, this non-constant set map must be continuous.

So if $X$ has more than 1 point and contractible, we get that $X$ is path connected but not connected. This is impossible, so $X$ must have one point if it were to be contractilbe.

Thanks!

8 – Creating an API via module routing files that includes csrf verification headers

I am working on migrating a custom API from D7 to D8 and am doing so by using module routing. I have a routing.yml file that looks like so:

ytp_user.api.login:
  path: "/api/v1/user/login"
  defaults:
    _title: "User API Login"
    _controller: 'Drupalytp_userControllerUserAPIController::login'
  methods: [POST]
  requirements:
    _csrf_request_header_token: "TRUE"
ytp_user.api.get_current_user:
  path: "/api/v2/user/me"
  defaults:
    _title: "User API Get Current User"
    _controller: 'Drupalytp_userControllerUserAPIController::getCurrentUser'
  methods: [GET]
  requirements:
    _custom_access: 'Drupalytp_userControllerUserAPIController::authorize'

In the first route, I am trying to validate a csrf token provided in the headers, via the requirement _csrf_request_header_token: "TRUE", however, this does absolutely nothing. It doesn’t validate or even check that the header exists as the documentation suggests it should.

I’ve tried replacing this with _csrf_token: 'TRUE' which at least checks that the token exists in the query, but I can’t get a valid token!!! If I grab a token from /session/token and then pass it along in the query as ?token=<token-from-session/token> then I just get an error saying the CSRF token is invalid.

Am I missing another step or is the documentation just straight up incorrect? I have been searching for hours and everything suggests that what I have should work, so why is the CSRF token not being validated properly?

My Hawaii “Safe Travels” COVID test is still stuck in “Verification in Process”. Is this a problem?

No, its not a problem. I’ve arrived in Hawaii with a “Verification in Process” test and was allowed to exit the airport without issues. From speaking to other people who have recently traveled to Hawaii, this is normal – they probably verify the test, but fail to update the portal with the right status.

calculus – Spivak Chapter 10, Exercise 19 solution verification. Prove that if $f^{(n)}(g(a))$ and $g^{(n)}(a)$ both exist, then $(fcirc g)^{(n)}(a)$ exists.

This question is asked here and here.

I’m going to try to answer it for my own edification, and for the next poor soul that comes across it and has trouble 🙂

I’m using Spivak’s Answer Book solution, but adding notes to hopefully clarify things.

Here goes:

From Calculus by Michael Spivak 3rd Edition, Chapter 10, Exercise 19.

10-19. Prove that if $f^{(n)}(g(a))$ and $g^{(n)}(a)$ both exist, then $(fcirc g)^{(n)}(a)$ exists. A little experimentation should convince you that it is unwise to seek a formula for $(fcirc g)^{(n)}(a)$. In order to prove that $(fcirc g)^{(n)}(a)$ exists you will therefore have to devise a reasonable assertion about $(fcirc g)^{(n)}(a)$ which can be proved by induction. Try something like: “$(fcirc g)^{(n)}(a)$ exists and is a sum of terms each of which is a product of terms of the form…”

First, let’s look at the first few derivatives of $(fcirc g)$. (These are calculated via straightforward application of the Chain Rule):

$$(fcirc g)^{prime}(x) = f^{prime}(g(x)) cdot g^{prime}(x)$$
$$(fcirc g)^{primeprime}(x) = f^{primeprime}(g(x)) cdot g^{prime}(x)^2 + f^{prime}(g(x)) cdot g^{primeprime}(x)$$
$$(fcirc g)^{primeprimeprime}(x) = f^{primeprimeprime}(g(x)) cdot g^{prime}(x)^3 + 3f^{primeprime}(g(x)) cdot g^{prime}(x)g^{primeprime}(x) + f^{prime}(g(x)) cdot g^{primeprimeprime}(x)$$

These suggest a general form for derivatives of $(fcirc g)$: the $n$-th derivative of $fcirc g$ seems to be made up of a sum of terms that are each the product of some constant, times some derivative of $f$ at $g(x)$, times some derivatives of $g$ at $x$, with these derivatives of $g$ perhaps raised to some power. None of the derivatives (of $f$ or $g$) are of order higher than $n$.

Conjecture: If $f^{(n)}(g(a))$ and $g^{(n)}(a)$ both exist, then $(fcirc g)^{(n)}(a)$ exists and is a sum of terms of the form
$$ccdot(g^{prime}(a))^{m_1}cdot(g^{primeprime}(a))^{m_2}cdots(g^{(n)}(a))^{m_n}cdot f^{(k)}(g(a))$$
for some number $c$, nonnegative integers $m_1,dots,m_n$ and a natural number $k leq n$.

(Aside: The conjecture concerns the existence of the derivative at a single point, $a$. It says, “if $g$ is $n$-times differentiable at $a$ and $f$ is $n$-times differentiable at $g(a)$, then $fcirc g$ is $n$-times differentiable at $a$. If there’s a second point $b$ such that $g$ is $n$-times differentiable at $b$ and $f$ is $n$-times differentiable at $g(b)$, then $fcirc g$ is $n$-times differentiable at $b$, and $(fcirc g)^{(n)}(b)$ is the sum of terms of the form
$$ccdot(g^{prime}(b))^{m_1}cdot(g^{primeprime}(b))^{m_2}cdots(g^{(n)}(b))^{m_n}cdot f^{(k)}(g(b))$$

where $c$, $m_1, dots, m_n$, $k$ in each term are all identical to the corresponding term for $(fcirc g)^{(n)}(a)$.)

Proof:
Let’s restate the conjecture we’re trying to prove.

Conjecture:
If $f^{(n)}(g(a))$ and $g^{(n)}(a)$ both exist, then $(fcirc g)^{(n)}(a)$ exists and is a sum of terms of the form

$$ccdot(g^{prime}(a))^{m_1}cdot(g^{primeprime}(a))^{m_2}cdots(g^{(n)}(a))^{m_n}cdot f^{(k)}(g(a))$$

Proof of the conjecture is by induction on $n$

Case for $n = 1$

If $f^{prime}(g(a))$ and $g^{prime}(a)$ both exist, then the Chain rule states that $(fcirc g)^{prime}(a)$ exists and is equal to $f^{prime}(g(a)) cdot g^{prime}(a)$.

Thus our conjecture is true for $n = 1$ (with $c = m_1 = k = 1$).

Case for $n + 1$

We will assume the conjecture is true for $n$, that is, if $f^{(n)}(g(a))$ and $g^{(n)}(a)$ both exist, then $(fcirc g)^{(n)}(a)$ exists and is a sum of terms of the form
$$ccdot(g^{prime}(a))^{m_1}cdot(g^{primeprime}(a))^{m_2}cdots(g^{(n)}(a))^{m_n}cdot f^{(k)}(g(a))$$

Note that we are not assuming that $(fcirc g)^{(n)}(a)$ exists. Our assumption is that if $f^{(n)}(g(a))$ and $g^{(n)}(a)$ both exist, then $(fcirc g)^{(n)}(a)$ exists.

(This distinction is important and sets this proof apart from inductive arguments I’ve previously encountered. Our assumption isn’t simply “thing is true”. Our assumption is that “if this condition is met, thing is true.” This is in agreement with the theorem we’re trying to prove. The theorem doesn’t say the $n$-th derivative of $fcirc g$ exists. Only that, if certain conditions are met, the derivative exists.)

Now we need to prove the conjecture for the $n + 1$ case. We need to show that if $f^{(n+1)}(g(a))$ and $g^{(n+1)}(a)$ both exist, then $(fcirc g)^{(n+1)}(a)$ exists, and is a sum of terms of the form

$$ccdot(g^{prime}(a))^{m_1}cdots(g^{(n+1)}(a))^{m_{n+1}}cdot f^{(k)}(g(a))$$

with $k leq n+1$.

Suppose $f^{(n+1)}(g(a))$ and $g^{(n+1)}(a)$ both exist.

This means that $f^{(n)}(y)$ exists for all $y$ in some interval around $g(a)$, and likewise $g^{(n)}(x)$ exists for all $x$ in some interval around $a$. Why? Because, by definition the $(n+1)$ derivatives are

$$f^{(n+1)}(g(a)) = lim_{y to g(a)}frac{f^{(n)}(y) – f^{(n)}(g(a))}{y-g(a)}$$
$$g^{(n+1)}(a) = lim_{x to a}frac{g^{(n)}(x) – g^{(n)}(a)}{x-a}$$

and in order for these limits to exist, the $n$-order derivatives must exist in some intervals around these points.

Furthermore, $f^{(k)}$ and $g^{(k)}$ must also exist in these intervals for all $1leq k < n$.

Because $f^{(n)}$ exists at and around $g(a)$, there is some $varepsilon_f > 0$ such that for all $y$ if $|y – g(a)| < varepsilon_f$, $f^{(n)}(y)$ exists. Likewise, since $g^{(n)}$ exists at and around $a$ there is some $delta_g >0$ such that for all $x$ if $|x-a| < delta_g$, $g^{(n)}(x)$ exists.

We know that $g$ is continuous at $a$ (it’s differentiable). As such there exists some $delta_f > 0$ such that for all $x$ if $|x-a| < delta_f$, then $|g(x) – g(a)| < varepsilon_f$. If we use $delta_{min} = min(delta_g,delta_f)$ then for all $x$ if $|x-a| < delta_{min}$, both $g^{(n)}(x)$ and $f^{(n)}(g(x))$ will exist.

In this interval both $g^{(n)}(x)$ and $f^{(n)}(g(x))$ exist, so the $n$-case assumption tells us $(fcirc g)^{(n)}(x)$ exists and is a sum of terms of the form

$$ccdot(g^{prime}(x))^{m_1}cdot(g^{primeprime}(x))^{m_2}cdots(g^{(n)}(x))^{m_n}cdot f^{(k)}(g(x))$$

Worth noting: we’re no longer only talking about the value of $(fcirc g)^{(n)}$ at a single point $a$. $(fcirc g)^{(n)}(x)$ exists for all $x$ in this interval around $a$.

$(fcirc g)^{(n)}$ is a function that’s defined at and around $a$. Furthermore, $(fcirc g)^{(n)}(x)$ is the sum of products of constants and derivatives of $f$ and $g$ and these derivatives are all themselves differentiable at $a$

Therefore, the derivative of $(fcirc g)^{(n)}$ at $a$ exists and can be calculated using the standard, sum, product and chain rules for derivatives.

Doing so will result in terms that look like either this

$$ccdot(g^{prime}(a))^{m_1}cdots m_{alpha}(g^{(alpha)}(a))^{m_{alpha}-1}cdot(g^{(alpha+1)}(a))^{m_{alpha+1}+1}cdots(g^{(n)}(a))^{m_n}cdot f^{(k)}(g(a))$$

this

$$ccdot(g^{prime}(a))^{m_1}cdots m_n(g^{(n)}(a))^{m_n-1}cdot(g^{(n+1)}(a))cdot f^{(k)}(g(a))$$

or this

$$ccdot(g^{prime}(a))^{m_1}cdots(g^{(n)}(a))^{m_n}cdot f^{(k+1)}(g(a))$$

all of which fit the required form for terms of the $n+1$ case.

Therefore, if $f^{(n+1)}(g(a))$ and $g^{(n+1)}(a)$ both exist, then $((fcirc g)^{(n)})^{prime}(a) = (fcirc g)^{(n+1)}(a)$ exists, and is a sum of terms of the form

$$ccdot(g^{prime}(a))^{m_1}cdots(g^{(n+1)}(a))^{m_{n+1}}cdot f^{(k)}(g(a))$$

with $k leq n+1$.

This completes the proof.
I hope.

automation – Scripts to repeatedly perform google search without asking for human verification

I am trying to write scripts to perform google search; however, once every 20-30 searches, google as us for human verification, which is very hard for a non-human agent to complete.

I tried the following things to avoid the human verification:

  1. Change LAN IP: Does not work at most of the times.

  2. Use a VPN to switch IP: works

  3. Change browser. It magically works!

What is the rationale behind the option 3? Do you know other methods or apps that works?

Do you think this will be a valid question on more professional SE sites like the stackoverflow?

combinatorics – number of injective and surjective functions? [verification]

Hello there’s a question where you need to find the total possible injective and surjective possibilities. I found a formula which you can use but don’t know for sure if it works for my example, could someone verify my answer? I’m almost certain of answer a, but want to know if b is correct?

If you know if its true can you reply, it would be very helpful. If it’s wrong could you explain why?

Thanks in advance

question

assume |X|=2 and |Y|=2016

a) How many injective functions are there from X to Y?
My answer = $frac{2016!}{2014!}$

b) How many surjective functions are there from Y to X?
My answer = $2^{2016}-2$

Formulas

  • injective = $frac{n!}{(n-m)!}$ from n => m
  • surjective = enter image description here

Trying to configure my NGINX file to add CORS policy, looking for some verification if I set up my config correctly

I’ve proxied my API that I use to pull data using nginx. I’ve configured it, it works just fine when I insert a URL request through a web-browser, HOWEVER, I get an issue when I request GET this data from the frontend.

Specifically this error:

Access to XMLHttpRequest at 'https://app.URL.io/data/path_to_data' from origin 'http://localhost:4000' has been blocked by CORS policy: Response to preflight request doesn't pass access control check: The 'Access-Control-Allow-Origin' header contains multiple values 'http://localhost:4000, http://localhost:4000/', but only one is allowed.

GET https://app.URL.io/data/path_to_data net::ERR_FAILED

http://localhost:4000/ is my frontend for reference.

here is my config file for nginx, the location of my API is /data/:

server {
    listen 80 default_server;
    listen [::]:80 default_server;
    server_name _;
    return 301 https://app.URL.io$request_uri;
}

server {
    listen [::]:443 ssl ipv6only=on;
    listen 443 ssl;
    server_name app.URL.io www.app.URL.io;

    # Let's Encrypt parameters
    ssl_certificate /etc/letsencrypt/live/app.URL.io/fullchain.pem;
    ssl_certificate_key /etc/letsencrypt/live/app.URL.io/privkey.pem;
    include /etc/letsencrypt/options-ssl-nginx.conf;
    ssl_dhparam /etc/letsencrypt/ssl-dhparams.pem;

    location = /favicon.ico { access_log off; log_not_found off; }


   location /static/ {
        alias /home/alpha/project;
    }


    location / {
        proxy_pass         http://unix:/run/gunicorn.sock;
        proxy_redirect     off;

        proxy_set_header   Host              $http_host;
        proxy_set_header   X-Real-IP         $remote_addr;
        proxy_set_header   X-Forwarded-For   $proxy_add_x_forwarded_for;
        proxy_set_header   X-Forwarded-Proto https;
    }

    # API LOCATED HERE
    location /data/ {
      default_type  application/json;
      proxy_hide_header Content-Location;
      add_header Content-Location  /data/$upstream_http_content_location;
      add_header Access-Control-Allow-Origin *;
      proxy_set_header  Connection "";
      proxy_http_version 1.1;
      proxy_pass http://localhost:3000/;
        }
}

To my understanding, I’ve set up the server correctly to satisfy browser CORS? Thank you for the help.