You may want to use curl and check for a 200 http status code , i.e.:
<?php
$url = 'http://arxiv.org/pdf/1207.41021.pdf';
$ch = curl_init($url);
curl_setopt($ch, CURLOPT_HEADER, true);    // we want headers
curl_setopt($ch, CURLOPT_NOBODY, true);    // we don't need body
curl_setopt($ch, CURLOPT_RETURNTRANSFER,1);
curl_setopt($ch, CURLOPT_FOLLOWLOCATION,1); // we follow redirections
curl_setopt($ch, CURLOPT_TIMEOUT,10);
$output = curl_exec($ch);
$httpcode = curl_getinfo($ch, CURLINFO_HTTP_CODE);
curl_close($ch);
if($httpcode == "200"){
    echo "file exist";
}else{
    echo "doesn't exist";
}
Both pdf files return 403 Forbidden
The server understood the request, but is refusing to fulfill it.
  Authorization will not help and the request SHOULD NOT be repeated. If
  the request method was not HEAD and the server wishes to make public
  why the request has not been fulfilled, it SHOULD describe the reason
  for the refusal in the entity. If the server does not wish to make
  this information available to the client, the status code 404 (Not
  Found) can be used instead.